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.
2022
RWC
A privacy attack on the SwissPost e-voting system
Abstract
The SwissPost e-voting system is currently proposed under the scrutiny of the community, before being deployed in 2022 for political elections in several Swiss cantons. We explain how real world constraints led to shortcomings that allowed a privacy attack to be mounted. More precisely, dishonest authorities can learn the vote of several voters of their choice, without being detected, even when the requested threshold of honest authorities act as prescribed.
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
Service
- Crypto 2025 Program committee
- Eurocrypt 2024 Program committee
- CiC 2024 Editor
- Eurocrypt 2022 Program committee
- PKC 2022 Program committee
- Eurocrypt 2017 Program committee
- PKC 2015 Program committee
- Asiacrypt 2013 Program committee
- Eurocrypt 2011 Program committee
Coauthors
- Kazumaro Aoki (1)
- Razvan Barbulescu (4)
- Joppe W. Bos (1)
- Fabrice Boudot (1)
- Cyril Bouvier (1)
- Olivier Chevassut (1)
- Veronique Cortier (1)
- Alexandre Debant (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 (24)
- 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)