CryptoDB
Pierrick Gaudry
Publications
Year
Venue
Title
2023
JOFC
Lattice Enumeration and Automorphisms for Tower NFS: A 521-Bit Discrete Logarithm Computation
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 $${{{\mathbb {F}}}}_{p^6}$$ F p 6 . The target finite field is of the same form as finite fields used in recent zero-knowledge proofs in some blockchains. This is the first reported implementation of TNFS.
2021
ASIACRYPT
Lattice Enumeration for Tower NFS: a 521-bit Discrete Logarithm Computation
📺
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.
2020
CRYPTO
Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment
📺
Abstract
We report on two new records: the factorization of RSA-240, a 795-bit number, and a discrete logarithm computation over a 795-bit prime field. Previous records were the factorization of RSA-768 in 2009 and a 768-bit discrete logarithm computation in 2016. Our two computations at the 795-bit level were done using the same hardware and software, and show that computing a discrete logarithm is not much harder than a factorization of the same size. Moreover, thanks to algorithmic variants and well-chosen parameters, our computations were significantly less expensive than anticipated based on previous records.
The last page of this paper also reports on the factorization of RSA-250.
2020
CRYPTO
Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields
📺
Abstract
We study the discrete logarithm problem at the boundary case between small and medium characteristic finite fields, which is precisely the area where finite fields used in pairing-based cryptosystems live. In order to evaluate the security of pairing-based protocols, we thoroughly analyze the complexity of all the algorithms that coexist at this boundary case: the Quasi-Polynomial algorithms, the Number Field Sieve and its many variants, and the Function Field Sieve. We adapt the latter to the particular case where the extension degree is composite, and show how to lower the complexity by working in a shifted function field. All this study finally allows us to give precise values for the characteristic asymptotically achieving the highest security level for pairings. Surprisingly enough, there exist special characteristics that are as secure as general ones.
2014
EUROCRYPT
2007
EUROCRYPT
2002
ASIACRYPT
Program Committees
- Eurocrypt 2022
- PKC 2022
- Eurocrypt 2017
- PKC 2015
- Asiacrypt 2013
- Eurocrypt 2011
Coauthors
- Kazumaro Aoki (1)
- Razvan Barbulescu (4)
- Joppe W. Bos (1)
- Fabrice Boudot (1)
- Cyril Bouvier (1)
- Olivier Chevassut (1)
- Jérémie Detrey (1)
- Iwan M. Duursma (1)
- Andreas Enge (2)
- Jean-Charles Faugère (1)
- Pierre-Alain Fouque (1)
- Mireille Fouquet (1)
- Jens Franke (1)
- Joshua Fried (1)
- Pierrick Gaudry (23)
- Aurore Guillevic (2)
- Nicolas Gürel (1)
- Robert Harley (1)
- Nadia Heninger (2)
- Florian Hess (1)
- T. Houtmann (1)
- Louise Huot (1)
- Hamza Jeljeli (1)
- Antoine Joux (1)
- Thorsten Kleinjung (2)
- David Kohel (2)
- Alexander Kruppa (1)
- Arjen K. Lenstra (1)
- Gabrielle De Micheli (3)
- Peter L. Montgomery (1)
- François Morain (2)
- Dag Arne Osvik (1)
- Cécile Pierrot (3)
- David Pointcheval (1)
- Guénaël Renault (1)
- Herman J. J. te Riele (1)
- Christophe Ritzenthaler (1)
- Éric Schost (1)
- Nigel P. Smart (1)
- Benjamin Smith (1)
- Emmanuel Thomé (6)
- Andrey Timofeev (1)
- Marion Videau (1)
- A. Weng (1)
- Paul Zimmermann (3)