HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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

Gabrielle de Micheli 1 Pierrick Gaudry 1 Cécile Pierrot 1
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry, Inria Nancy - Grand Est
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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03242324
Contributor : Pierrick Gaudry Connect in order to contact the contributor
Submitted on : Thursday, January 6, 2022 - 5:18:48 PM
Last modification on : Thursday, May 5, 2022 - 10:03:45 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

Citation

Gabrielle de Micheli, Pierrick Gaudry, Cécile Pierrot. Lattice Enumeration for Tower NFS: a 521-bit Discrete Logarithm Computation. ASIACRYPT 2021 - 27th Annual International Conference on the Theory and Application of Cryptology and Information Security, Dec 2021, Virtual, Singapore. pp.67-96, ⟨10.1007/978-3-030-92062-3_3⟩. ⟨hal-03242324v2⟩

Share

Metrics

Record views

99

Files downloads

89