New discrete logarithm records, and the death of Type 1 pairings

In the last few days there have been several announcements of record-breaking discrete logarithm computations:

All these papers are using the algorithmic ideas introduced by Joux and others in 2013.

The third result listed above is a continuation of the sort of records previously announced, in particular, since 9234 = 18 * 513 and 513 = 2^9 + 1, it is again using “twisted Kummer” extensions over GF( 2^9 ). This result breaks by a large margin the previous world-record for finite field discrete logarithm computations. It is a great result.

However, the first two results are particularly interesting from the point of view of pairing-based cryptography. Both of the computations are for fields that very naturally arise in pairing-based cryptography using supersingular curves. Importantly, the “large prime” in the field size is not a power of 2 plus or minus 1. Hence these records have shown that the new algorithmic ideas can be applied to a wider range of fields than the previous computations might suggest. This gives evidence that all supersingular elliptic and hyperelliptic curves over moderately-sized fields of small characteristic are not secure for pairing-based cryptography.

One interesting consequence of these works is that “Type 1″ pairings are now essentially dead. Recall that Galbraith, Paterson and Smart “Pairings for cryptographers” (Discrete Applied Mathematics, 2008) introduced a classification of pairings into Type 1, Type 2 and Type 3 (there is also a Type 4, but it is rarely used). Type 3 pairings are usually the most efficient, but some authors have preferred Type 1 pairings as they are convenient in certain applications. Hence, there are a lot of cryptographic protocols in the literature that have been designed only for Type 1 pairings.

The main way to implement Type 1 pairings is to use supersingular curves. There are traditionally two choices:

  1. using fields of characteristic 2 or 3;
  2. using supersingular elliptic curves (embedding degree 2) over GF( p ) where p is at least a 500-bit prime (and, nowadays, probably at least a 1500-bit prime).

The first option was by far the most efficient, but the recent discrete logarithm algorithms and computational records mean it must now be considered insecure. Hence we are stuck with the relatively slow choice of elliptic curves over GF( p ). It means that Type 1 pairings will now be much much slower than Type 3 pairings. It would be better in future to design protocols that do not require Type 1 pairings.

One technical remark:  One can implement Type 1 pairings using ordinary elliptic curves over any field.  One works in a subgroup that is not an eigenspace for Frobenius, and uses the trace map as a “distortion map” to ensure a non-degenerate pairing.  However this approach is also extremely inconvenient: there is no compact representation for elliptic curve points, and the pairing computation is also slow.  So the claim that Type 1 pairings are dead remains true.

— Steven Galbraith

About these ads
This entry was posted in Uncategorized. Bookmark the permalink.

3 Responses to New discrete logarithm records, and the death of Type 1 pairings

  1. How about the type-1 constructions proposed at Pairing 2013?

    Tadanori Teruya,Kazutaka Saito,Naoki Kanayama,Yuto Kawahara, Tetsutaro
    Kobayashi, Eiji Okamoto: “Constructing Symmetric Pairings over Supersingular
    Elliptic Curves with Embedding Degree Three”


    Xusheng Zhang,Kunpeng Wang: “Fast Symmetric Pairing Revisited”

  2. ellipticnews says:

    It is true that one can also use embedding degree 3 for Type 1 pairings. Thanks for listing some references. But the primes still need to be quite large and I guess the pairing is a bit slow compared with BN curves etc.

  3. Pingback: DLP workshop, Ascona | ellipticnews

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s