Team : ALMASTY

Departure date : 12/31/2016

This thesis focuses on the discrete logarithm problem in the multiplicative group of invertible elements of a finite field.

First we propose a quasipolynomial time algorithm build upon Frobenius representation of the target field that permits to solve the problem if the characteristic is small, with respect to the whole order of the field. In practice and for instance, the current discrete logarithm record in characteristic 3 uses this result.

For medium or large characteristics finite fields, another approach is required. So we present the multiple number field sieve (MNFS) that reaches the best asymptotic heuristic complexities for this double range of characteristics. Last but not least, we also introduce the notion of nearly sparse matrices. Designing a new algorithm dedicated to explicitly give the kernel of such a matrix eases in practice the linear algebra step of any variant of the number field sieve.

Reynald Lercier (Université Rennes 1) [rapporteur]

Daniel Augot (Inria, Ecole Polytechnique)

Ronald Cramer (CWI, Amsterdam)

Guillaume Hanrot (ENS Lyon)

Antoine Joux (Fondation partenariale de l'UPMC)

Ariane Mézard (UPMC)

David Naccache (ENS Paris)

- 2016
- A. Joux, C. Pierrot : “Technical history of discrete logarithms in small characteristic finite fields : The road from subexponential to quasi-polynomial complexity”, Designs, Codes and Cryptography, vol. 78 (1), pp. 73-85, (Springer Verlag) (2016)
- C. Pierrot, B. Wesolowski : “Malleability of the blockchain’s entropy”, ArcticCrypt 2016, Longyearbyen, Norway (2016)
- A. Joux, C. Pierrot : “Nearly Sparse Linear Algebra and application to Discrete Logarithms Computations”, chapter in Contemporary Developments in Finite Fields and Applications, (World Scientific) (2016)
- C. Pierrot : “Le logarithme discret dans les corps finis”, these, defence 11/25/2016, supervision Joux, Antoine (2016)

- 2015
- C. Pierrot : “The Multiple Number Field Sieve with Conjugation and Generalized Joux-Lercier Methods”, Eurocrypt, vol. 9056, Lecture Notes in Computer Science, Sofia, Bulgaria, pp. 156-170, (Springer) (2015)

- 2014
- A. Joux, C. Pierrot : “Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms - Simplified Setting for Small Characteristic Finite Fields”, 20
^{th}International Conference on the Theory and Application of Cryptology and Information Security, vol. 8873, Lecture Notes in Computer Science, Kaoshiung, Taiwan, pp. 378-397, (Springer Berlin Heidelberg), (ISBN: 978-3-662-45610-1) (2014)

- A. Joux, C. Pierrot : “Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms - Simplified Setting for Small Characteristic Finite Fields”, 20
- 2013
- A. Joux, C. Pierrot : “The Special Number Field Sieve in $\F _p^n$, Application to Pairing-Friendly Constructions”, 6
^{th}International Conference on Pairing-based Cryptography, Pairing 2013, vol. 8365, Lecture Notes in Computer Science, Beijing, China, pp. 45-61, (Springer International Publishing), (ISBN: 978-3-319-04872-7) (2013)

- A. Joux, C. Pierrot : “The Special Number Field Sieve in $\F _p^n$, Application to Pairing-Friendly Constructions”, 6