Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  Horst Lemke Apr 28 at 12:50
    
@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. –  DrLecter Apr 28 at 13:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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