International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Pierrick Gaudry

Publications

Year
Venue
Title
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
EPRINT
2015
EPRINT
2015
EUROCRYPT
2015
ASIACRYPT
2014
EUROCRYPT
2014
PKC
2014
JOFC
2011
JOFC
2011
ASIACRYPT
2010
EPRINT
Factorization of a 768-bit RSA modulus
This paper reports on the factorization of the 768-bit number RSA-768 by the number field sieve factoring method and discusses some implications for RSA.
2010
EPRINT
A Low-Area yet Performant FPGA Implementation of Shabal
In this paper, we present an efficient FPGA implementation of the SHA-3 hash function candidate Shabal. Targeted at the recent Xilinx Virtex-5 FPGA family, our design achieves a relatively high throughput of 2 Gbit/s at a cost of only 153 slices, yielding a throughput-vs.-area ratio of 13.4 Mbit/s per slice. Our work can also be ported to Xilinx Spartan-3 FPGAs, on which it supports a throughput of 800 Mbit/s for only 499 slices, or equivalently 1.6 Mbit/s per slice. According to the SHA-3 Zoo website, this work is among the smallest reported FPGA implementations of SHA-3 candidates, and ranks first in terms of throughput per area.
2010
CRYPTO
2008
EPRINT
The arithmetic of characteristic 2 Kummer surfaces
P. Gaudry D. Lubicz
The purpose of this paper is a description of a model of Kummer surfaces in characteristic 2, together with the associated formulas for the pseudo-group law. Since the classical model has bad reduction, a renormalization of the parameters is required, that can be justified using the theory of algebraic theta functions. The formulas that are obtained are very efficient and may be useful in cryptographic applications. We also show that applying the same strategy to elliptic curves gives Montgomery-like formulas in odd characteristic that are of some interest, and we recover already known formulas by Stam in characteristic 2.
2007
EUROCRYPT
2006
ASIACRYPT
2006
PKC
2005
EPRINT
Key Derivation and Randomness Extraction
Key derivation refers to the process by which an agreed upon large random number, often named master secret, is used to derive keys to encrypt and authenticate data. Practitioners and standardization bodies have usually used the random oracle model to get key material from a Diffie-Hellman key exchange. However, proofs in the standard model require randomness extractors to formally extract the entropy of the random master secret into a seed prior to derive other keys. This paper first deals with the protocol $\Sigma_0$, in which the key derivation phase is (deliberately) omitted, and security inaccuracies in the analysis and design of the Internet Key Exchange (IKE version 1) protocol, corrected in IKEv2. They do not endanger the practical use of IKEv1, since the security could be proved, at least, in the random oracle model. However, in the standard model, there is not yet any formal global security proof, but just separated analyses which do not fit together well. The first simplification is common in the theoretical security analysis of several key exchange protocols, whereas the key derivation phase is a crucial step for theoretical reasons, but also practical purpose, and requires careful analysis. The second problem is a gap between the recent theoretical analysis of HMAC as a good randomness extractor (functions keyed with public but random elements) and its practical use in IKEv1 (the key may not be totally random, because of the lack of clear authentication of the nonces). Since the latter problem comes from the probabilistic property of this extractor, we thereafter review some \textit{deterministic} randomness extractors and suggest the \emph{'Twist-AUgmented'} technique, a new extraction method quite well-suited for Diffie-Hellman-like scenarios.
2005
EPRINT
Fast genus 2 arithmetic based on Theta functions
P. Gaudry
In 1986, D. V. Chudnovsky and G. V. Chudnovsky proposed to use formulae coming from Theta functions for the arithmetic in Jacobians of genus 2 curves. We follow this idea and derive fast formulae for the scalar multiplication in the Kummer surface associated to a genus 2 curve, using a Montgomery ladder. Our formulae can be used to design very efficient genus 2 cryptosystems that should be faster than elliptic curve cryptosystems in some hardware configurations.
2004
EUROCRYPT
2004
EPRINT
Index calculus for abelian varieties and the elliptic curve discrete logarithm problem
Pierrick Gaudry
We propose an index calculus algorithm for the discrete logarithm problem on general abelian varieties. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve all elliptic curve discrete logarithm problems defined over $GF(q^3)$ in time $O(q^{10/7})$, with a reasonably small constant; and an elliptic problem over $GF(q^4)$ or a genus 2 problem over $GF(p^2)$ in time $O(q^{14/9})$ with a larger constant.
2004
EPRINT
A double large prime variation for small genus hyperelliptic index calculus
In this article, we examine how the index calculus approach for computing discrete logarithms in small genus hyperelliptic curves can be improved by introducing a double large prime variation. Two algorithms are presented. The first algorithm is a rather natural adaptation of the double large prime variation to the intended context. On heuristic and experimental grounds, it seems to perform quite well but lacks a complete and precise analysis. Our second algorithm is a considerably simplified variant, which can be analyzed easily. The resulting complexity improves on the fastest known algorithms. Computer experiments show that for hyperelliptic curves of genus three, our first algorithm surpasses Pollard's Rho method even for rather small field sizes.
2002
ASIACRYPT
2002
JOFC
2001
ASIACRYPT
2001
EUROCRYPT
2000
EUROCRYPT
1999
ASIACRYPT

Program Committees

Eurocrypt 2017
PKC 2015
Asiacrypt 2013
Eurocrypt 2011