Paper 2013/737

Weakness of F_{3^{6*1429}} and F_{2^{4*3041}} for Discrete Logarithm Cryptography

Gora Adj, Alfred Menezes, Thomaz Oliveira, and Francisco Rodriguez-Henriquez

Abstract

In 2013, Joux and then Barbulsecu et al. presented new algorithms for computing discrete logarithms in finite fields of small characteristic. Shortly thereafter, Adj et al. presented a concrete analysis showing that, when combined with some steps from classical algorithms, the new algorithms render the finite field F_{3^{6*509}} weak for pairing-based cryptography. Granger and Zumbragel then presented a modification of the new algorithms that extends their effectiveness to a wider range of fields. In this paper, we study the effectiveness of the new algorithms combined with a carefully crafted descent strategy for the fields F_{3^{6*1429}} and F_{2^{4*3041}}. The intractability of the discrete logarithm problem in these fields is necessary for the security of pairings derived from supersingular curves with embedding degree 6 and 4 defined, respectively, over F_{3^{1429}} and F_{2^{3041}}; these curves were believed to enjoy a security level of 192 bits against attacks by Coppersmith's algorithm. Our analysis shows that these pairings offer security levels of at most 96 and 129 bits, respectively, leading us to conclude that they are dead for pairing-based cryptography.

Note: Corrected the descent tree for GF(3^{12*1429}).

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
ajmeneze @ uwaterloo ca
History
2013-12-01: last of 3 revisions
2013-11-14: received
See all versions
Short URL
https://ia.cr/2013/737
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/737,
      author = {Gora Adj and Alfred Menezes and Thomaz Oliveira and Francisco Rodriguez-Henriquez},
      title = {Weakness of F_{3^{6*1429}} and F_{2^{4*3041}} for Discrete Logarithm Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2013/737},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/737}},
      url = {https://eprint.iacr.org/2013/737}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.