Joux kills pairings in characteristic 2

Antoine Joux has announced a new discrete logarithm record. This time the field is GF( 2^(257*24)). The computation took about “550 CPU hours” (i.e., less than a month on one CPU). As is typical for this new type of algorithm, the majority of the computation was in the descent step, rather than in linear algebra or relation collection.

The relevance for pairing-based cryptography is the following: If one was using supersingular curves (of genus 1 or 2) in characteristic 2 then one would have a group over GF( 2^p ) for some prime (e.g., p = 257) and the pairing would map into an extension of this field of degree 4 or 12.  Hence, the target group would be contained in the multiplicative group of GF( 2^(p*24)). Parameters of this size, or even smaller, have been proposed previously in the literature (such as in my “eta pairing” paper with Barreto, O’hEigeartaigh and Scott). The fact that such a large discrete log instance can be solved in a relatively short time has major impact on the security of pairings in small characteristic. The parameters in the eta pairing paper should not be used. It seems prudent now to use pairings only in large prime characteristic for all practical applications.

  — Steven Galbraith

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Joux kills pairings in characteristic 2

  1. Robert Granger says:

    Hi Steven, I agree that using small characteristic pairings are a bad idea now. However, I don’t think the coffin has been firmly nailed shut just yet!

    In particular, the two recent breaks – Joux’s in GF(2^(24*257)) and our earlier one in GF(2^(24*255)) (announced here https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;fe9605d9.1304) – are very special cases which are far easier to break than other extensions of GF(2^24) of a similar size, for which one needs a more complicated extension-defining polynomial than X^256 = aX^{\pm 1}, which then kills much of the factor base reduction achievable via automorphisms. Furthermore, the descent then becomes slower as well. So attacking a really interesting case such as SS curves over GF(2^1223) will take considerably more work.

  2. ellipticnews says:

    That’s a good comment Rob. But these results still make char 2 pairings hard to sell. If you were proposing curves in char 2 for pairings then you would need to provide an explicit justification of why the parameters resist the new index calculus algorithms in the finite field. It is a bit like people proposing composite extension fields for standard ECC (which still happens from time to time): they need to justify why such fields are not vulnerable to known Weil descent attacks. Such arguments can probably be made, but they will always be treated with scepticism and caution.

    — Steven Galbraith

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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