## CryptoDB

### Pierrick Gaudry

#### Publications

**Year**

**Venue**

**Title**

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

2010

EPRINT

Factorization of a 768-bit RSA modulus
Abstract

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
Abstract

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.

2008

EPRINT

The arithmetic of characteristic 2 Kummer surfaces
Abstract

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

2005

EPRINT

Key Derivation and Randomness Extraction
Abstract

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
Abstract

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

EPRINT

Index calculus for abelian varieties and the elliptic curve discrete logarithm problem
Abstract

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
Abstract

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

#### Program Committees

- Eurocrypt 2017
- PKC 2015
- Asiacrypt 2013
- Eurocrypt 2011

#### Coauthors

- Kazumaro Aoki (2)
- Razvan Barbulescu (5)
- Joppe W. Bos (2)
- Fabrice Boudot (1)
- Cyril Bouvier (1)
- Olivier Chevassut (2)
- Jérémie Detrey (2)
- Claus Diem (1)
- Iwan M. Duursma (1)
- Andreas Enge (2)
- Jean-Charles Faugère (1)
- Pierre-Alain Fouque (2)
- Mireille Fouquet (1)
- Jens Franke (2)
- Joshua Fried (1)
- Steven D. Galbraith (1)
- 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)
- Karim Khalfallah (1)
- Thorsten Kleinjung (4)
- David Kohel (2)
- Alexander Kruppa (2)
- Arjen K. Lenstra (2)
- David Lubicz (1)
- Gabrielle De Micheli (2)
- Peter L. Montgomery (2)
- François Morain (2)
- Dag Arne Osvik (2)
- Cécile Pierrot (2)
- David Pointcheval (2)
- Guénaël Renault (1)
- Herman J. J. te Riele (2)
- Christophe Ritzenthaler (1)
- Éric Schost (1)
- Nigel P. Smart (1)
- Benjamin Smith (1)
- Nicolas Thériault (1)
- Emmanuel Thomé (8)
- Andrey Timofeev (2)
- Marion Videau (1)
- A. Weng (1)
- Paul Zimmermann (4)