Paper 2016/605

Improving NFS for the discrete logarithm problem in non-prime finite fields

Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, and François Morain

Abstract

The aim of this work is to investigate the hardness of the discrete logarithm problem in fields GF($p^n$) where $n$ is a small integer greater than $1$. Though less studied than the small characteristic case or the prime field case, the difficulty of this problem is at the heart of security evaluations for torus-based and pairing-based cryptography. The best known method for solving this problem is the Number Field Sieve (NFS). A key ingredient in this algorithm is the ability to find good polynomials that define the extension fields used in NFS. We design two new methods for this task, modifying the asymptotic complexity and paving the way for record-breaking computations. We exemplify these results with the computation of discrete logarithms over a field GF($p^2$) whose cardinality is 180 digits (595 bits) long.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2015
DOI
10.1007/978-3-662-46800-5_6
Keywords
Discrete logarithm computationNFS
Contact author(s)
guillevic @ lix polytechnique fr
History
2016-06-10: received
Short URL
https://ia.cr/2016/605
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/605,
      author = {Razvan Barbulescu and Pierrick Gaudry and Aurore Guillevic and François Morain},
      title = {Improving NFS for the discrete logarithm problem in non-prime finite fields},
      howpublished = {Cryptology ePrint Archive, Paper 2016/605},
      year = {2016},
      doi = {10.1007/978-3-662-46800-5_6},
      note = {\url{https://eprint.iacr.org/2016/605}},
      url = {https://eprint.iacr.org/2016/605}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.