New finite field discrete log record.

NICT, Kyushu University and Fujitsu Laboratories Achieve World Record Cryptanalysis of Next-Generation Cryptography.

The computation is a function field sieve algorithm for the field GF( 3^(6*97) ). This field is of interest for pairing-based cryptography, as there is a supersingular embedding degree 6 curve over GF( 3^97 ) with near-prime order.

This builds on previous work by these groups, for example see:

Takuya Hayashi, Naoyuki Shinohara, Lihua Wang, Shin’ichiro Matsuo, Masaaki Shirase, Tsuyoshi Takagi: Solving a 676-Bit Discrete Logarithm Problem in GF(3^(6n)). IEICE Transactions 95-A(1): 204-212 (2012) , and lso their paper at Public Key Cryptography 2010 (Springer LNCS 6056) 351-367.

It is a very good result — well done!

— Steven Galbraith

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

4 Responses to New finite field discrete log record.

  1. Two remarks I should have mentioned:
    1. The result means they can also solve the DLP on the supersingular elliptic curve E( F_{3^{97}} ), which is a new ECDLP record.
    2. The press release somehow implies that pairing-based cryptography is “fragile”. This is not true. The consequence that if you want to use characteristic 2 or 3 (e.g., for the eta pairing) then you need to use a much larger field, or else use totally different curves (such as Barreto-Naehrig curves, which are over fields of much larger characteristic).

    — Steven Galbraith

    • Kenny Paterson says:

      Good that you clarified this aspect. The press release is sufficiently mangled that I’ve been getting alarmed questions from various people.

  2. ellipticnews says:

    The authors themselves have provided estimates of the security of characteristic 3 finite fields:

    Key Length Estimation of Pairing-based Cryptosystems using $\eta_T$ Pairing
    Naoyuki Shinohara and Takeshi Shimoyama and Takuya Hayashi and Tsuyoshi Takagi
    http://eprint.iacr.org/2012/042

    From this we see that pairings in characteristic 3 are not providing the security we would have liked.

  3. Pingback: Asiacrypt 2012 | ellipticnews

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