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

- Computing Discrete Logarithms in F_{3^{6*137}} using Magma by Gora Adj, Alfred Menezes, Thomaz Oliveira and Francisco Rodriguez-Henriquez. (January 26,2014)
- Discrete Logarithms in the Jacobian of a genus 2 supersingular curve over GF(2^367) by Robert Granger, Thorsten Kleinjung and Jens Zumbragel. (January 30, 2014)
This looks like a paper about hyperelliptic curves, but it is really about discrete logarithms in the field GF(2^4404) = GF(2^(12*367)). Note that the computation also shows that a popular supersingular curve for pairings (over GF( 2^367 ), and with embedding degree 4) is weak.

- Discrete Logarithms in GF(2^9234), again by Robert Granger, Thorsten Kleinjung and Jens Zumbragel. (January 31, 2014)

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:

- using fields of characteristic 2 or 3;
- 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

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”

and

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

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.

Pingback: DLP workshop, Ascona | ellipticnews