Paper 2021/707

Lattice Enumeration for Tower NFS: a 521-bit Discrete Logarithm Computation

Gabrielle De Micheli, Pierrick Gaudry, and Cécile Pierrot

Abstract

The Tower variant of the Number Field Sieve (TNFS) is known to be asymptotically the most efficient algorithm to solve the discrete logarithm problem in finite fields of medium characteristics, when the extension degree is composite. A major obstacle to an efficient implementation of TNFS is the collection of algebraic relations, as it happens in dimension greater than 2. This requires the construction of new sieving algorithms which remain efficient as the dimension grows. In this article, we overcome this difficulty by considering a lattice enumeration algorithm which we adapt to this specific context. We also consider a new sieving area, a high-dimensional sphere, whereas previous sieving algorithms for the classical NFS considered an orthotope. Our new sieving technique leads to a much smaller running time, despite the larger dimension of the search space, and even when considering a larger target, as demonstrated by a record computation we performed in a 521-bit finite field GF(p^6). The target finite field is of the same form than finite fields used in recent zero-knowledge proofs in some blockchains. This is the first reported implementation of TNFS.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
discrete logarithm problemcryptanalysis
Contact author(s)
pierrick gaudry @ loria fr
History
2021-05-31: revised
2021-05-28: received
See all versions
Short URL
https://ia.cr/2021/707
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/707,
      author = {Gabrielle De Micheli and Pierrick Gaudry and Cécile Pierrot},
      title = {Lattice Enumeration for Tower NFS: a 521-bit Discrete Logarithm Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2021/707},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/707}},
      url = {https://eprint.iacr.org/2021/707}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.