Direction de recherche : Antoine JOUX

Le logarithme discret dans les corps finis

La cryptologie consiste en l’étude des techniques utilisées par deux entités pour communiquer en secret en présence d’une troisième. Ces techniques sont conçues autour de problèmes calculatoires réputés difficiles. Les propriétés mathématiques sous-jacentes à ces problèmes garantissent que l’attaque de tels algorithmes reste infaisable en pratique par un adversaire malveillant. Ainsi, les protocoles cryptographiques s’appuient sur diverses hypothèses, comme la difficulté présumée de factoriser de grands entiers, ou de calculer le logarithme discret d’un élément arbitraire dans certains groupes.
Cette thèse porte sur l’étude du problème du logarithme discret dans le groupe multiplicatif des éléments inversibles d'un corps fini.
Dans cet exposé nous proposerons un algorithme quasipolynomial par représentation de Frobenius, qui permet de résoudre le problème si le corps présente une caractéristique de petite taille, relativement à l’ordre total de celui-ci. En pratique et pour l'exemple, le record actuel de calcul de logarithme discret en caractéristique 3 fait maintenant appel à ce résultat.
Lorsque la caractéristique grandit, une autre méthode est requise. Nous présenterons d'abord le crible par corps de nombres multiples (MNFS) qui obtient à ce jour les complexités asymptotiques les plus basses pour un corps arbitraire de moyenne ou grande caractéristique. Enfin, nous introduirons la notion de matrice presque creuse, pour esquisser les grandes lignes d’un algorithme spécifique permettant d’expliciter le noyau d’une telle matrice. En pratique, celui-ci facilite l’étape d’algèbre linéaire sous-jacente à toute variante du crible par corps de nombres.

Publications 2013-2016

• 2016
  • C. Pierrot : “Le logarithme discret dans les corps finis”, thèse, soutenance 25/11/2016, direction de recherche 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)