14
$\begingroup$

I'm currently testing one among those many interesting cryptographic protocols based on bilinear maps. It's quite hard to understand the underlying fundamentals, especially since there are several types of pairing and different underlying algorithms like Weil, Tate and Ate (again with subtypes?). Although I understand the properties

So I started with Ben Lynn's "On The Implementation of pairing based cryptosystems", which is relatively old. There he distinguishes between Type A-G curves and notes that Type3 curves are "susceptible to certain discrete log attacks". On the other hand, Steven Galbraith talks about "the death of Type 1 pairings" in his quite new blog entry and states that "Type 3 pairings are usally the most efficient" and Type 4 is rarly used. (Ben Lynn however seemed to have a little preference for the Type 4 pairing) Are those the same pairings as mentioned by Ben Lynn?

Can some of them been seen als secure enough for productive use? Are some of them seen to be more secure than others? What about the Ate-pairing which seems to be surprisingly fast?

$\endgroup$

1 Answer 1

15
$\begingroup$

Type-1 (symmetric pairings) are dead for curves over fields of small characteristic. Over prime fields of large prime characteristic they are not really dead, but as they only offer small embedding degrees ($k=2$), they are not really attractive from a performance point of view. You have to choose very large curves (which makes the curve arithmetic slow) such that you have a reasonable security in the multiplicative target group.

Type-3 pairings are most attractive (from the perspective of a performance and security tradeoff) as when they are used with Barreto-Naehrig (BN) curves, they have nice embedding degree of 12 (meaning that for 256 bit curve $G_1$ will give you 3072 bit in $G_T$ and this choice is ideal at the 128bit security level w.r.t. the comparable strengths proposed by NIST at the moment). Furthermore, most Type-2 protocols can be ported to the Type-3 setting by non-crucial modifications.

Type-4 are rarely used as they only are required if one requires secure hashing (in the sense that one does not know the discrete logarithm of the result to some fixed point) to $G_2$ (and that is only required rarely by protocols). As it turned out, they are also quite dangerous to use.

The different types of pairing functions $e$ (ate, optimal-ate, etc.) are basically all instantiations of the miller algorithm (aka miller loop) with different optimizations (use of distortion maps, use of Forbenius, etc. in the algorithm) and are typically restricted by the type of paring you are using.

Benn Lynn actually provides Type-3 pairings (dn - MNT curves, f - BN curves) and I have no idea why it seems that he has a preference towards Type-4 (maybe because he required them in his proposed protocols?).

I think whether they are ready for productive use is opinion-based, but AFAIK Voltage sells pairing-based crypto for years, and there are also draft standards for IEEE P1363 and I guess they will propose the use of BN curves. Also there is a draft RFC on the Optimal Ate pairing over BN curves.

Udate: Since there has been a recent progress in the discrete logarithm problem in extensions of fields of large prime characteristic (see here for a nice overview), it is not really clear at the moment how exactly this would influence BN curve choices to adjust the BN curve parameters for a given security parameter. It is thus possible that for instance KSS curves (with an embedding degree of $k=18$) get more attractive than BN curvres. So this will not really push standardization at the moment till this is clear.

$\endgroup$
4
  • $\begingroup$ Ok, so my mistake was to think Lynn's Type F curve is equal to a type 4 pairing. What I ment by ready for productive environments is, how likely are the discovery for other discrete logarithms or inverse pairings. Of course, nobody can tell a number, however so far as I Know, the Same question was responsible for the long time ECC took to be accepted. $\endgroup$ Apr 28, 2014 at 12:50
  • $\begingroup$ @Horst Lemke Which type (2,3,4) you actually have depends on how $G_2$ is chosen and I do not see how this is defined for pbc. It turned out that type 4 can be dangerous and is typically not required (only for few protocols). You may find this interesting as an overview. Unfortunately, I think how likely these discoveries are is hard to tell. At least for type 2 and type 3 setting working over ordinary (and not supersingular) curves over fields of large prime characteristic dl progress will likely doom ECC in general. $\endgroup$
    – DrLecter
    Apr 28, 2014 at 13:46
  • $\begingroup$ Could you please refer to an article which explains different types of pairings? I'm a bit familiar with type-I and type-III but what is the fourth type?! $\endgroup$
    – Habib
    Nov 6, 2014 at 17:25
  • 1
    $\begingroup$ @Habib As far as I remember "Pairings for Cryptographers" gives a high level overview of all those types. There is also a paper "On the Efficiency and Security of Pairing-Based Protocols in the Type 1 and Type 4 Settings" discussing Type 4 pairings. $\endgroup$
    – DrLecter
    Nov 6, 2014 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.