Weakness of F_{3^{6*509}} for Discrete Logarithm Cryptography

Gora Adj; Alfred Menezes; Thomaz Oliveira; Francisco Rodríguez-Henríquez

Paper 2013/446

Weakness of F_{3^{6*509}} for Discrete Logarithm Cryptography

Gora Adj, Alfred Menezes, Thomaz Oliveira, and Francisco Rodríguez-Henríquez

Abstract

In 2013, Joux, and then Barbulescu, Gaudry, Joux and Thomé, presented new algorithms for computing discrete logarithms in finite fields of small and medium characteristic. We show that these new algorithms render the finite field F_{3^{6*509}} = F_{3^{3054}} weak for discrete logarithm cryptography in the sense that discrete logarithms in this field can be computed significantly faster than with the previous fastest algorithms. Our concrete analysis shows that the supersingular elliptic curve over F_{3^{509}} with embedding degree 6 that had been considered for implementing pairing-based cryptosystems at the 128-bit security level in fact provides only a significantly lower level of security. Our work provides a convenient framework and tools for performing a concrete analysis of the new discrete logarithm algorithms and their variants.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown status
Contact author(s): francisco @ cs cinvestav mx
History: 2013-12-01: last of 5 revisions; 2013-07-22: received; See all versions
Short URL: https://ia.cr/2013/446
License: CC BY

BibTeX

@misc{cryptoeprint:2013/446,
      author = {Gora Adj and Alfred Menezes and Thomaz Oliveira and Francisco Rodríguez-Henríquez},
      title = {Weakness of F_{3^{6*509}} for Discrete Logarithm Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/446},
      year = {2013},
      url = {https://eprint.iacr.org/2013/446}
}