International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Pierrick Gaudry

Publications

Year
Venue
Title
2023
JOFC
Lattice Enumeration and Automorphisms for Tower NFS: A 521-Bit Discrete Logarithm Computation
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 📺
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 📺
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 📺
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.
2017
EUROCRYPT
2015
EUROCRYPT
2015
ASIACRYPT
2014
EUROCRYPT
2014
PKC
2014
JOFC
2011
JOFC
2011
ASIACRYPT
2010
CRYPTO
2007
EUROCRYPT
2006
ASIACRYPT
2006
PKC
2004
EUROCRYPT
2002
ASIACRYPT
2002
JOFC
2001
ASIACRYPT
2001
EUROCRYPT
2000
EUROCRYPT
1999
ASIACRYPT

Program Committees

Eurocrypt 2022
PKC 2022
Eurocrypt 2017
PKC 2015
Asiacrypt 2013
Eurocrypt 2011