Supervision : Antoine JOUX

Discrete logarithm in finite fields

Cryptography is the study of techniques for secure communication in the presence of third parties, also called adversaries. Such techniques are designed around computational hardness assumptions related to mathematical properties, making such algorithms hard to break in practice by any adversary. These protocols are based on the computational difficulty of various problems which often come from number theory, such as integer factorization or discrete logarithms computations.
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.

2013-2016 Publications

• 2016
  • C. Pierrot : “Le logarithme discret dans les corps finis”, thesis, defence 11/25/2016, supervision Joux, Antoine (2016)
  • C. Pierrot, B. Wesolowski : “Malleability of the blockchain’s entropy”, ArcticCrypt 2016, Longyearbyen, Norway (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)
  • A. Joux, C. Pierrot : “Nearly Sparse Linear Algebra and application to Discrete Logarithms Computations”, chapter in Contemporary Developments in Finite Fields and Applications, (ISBN: 978-981-4719-27-8) (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, Province of China, pp. 378-397, (Springer Berlin Heidelberg) (2014)
• 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) (2013)