Direction de recherche : Jean-Charles FAUGÈRE
Co-encadrement : VITSE Vanessa

Le problème de décomposition de points dans les variétés Jacobiennes

Le problème du logarithme discret est une brique fondamentale de nombreux protocoles de communication sécurisée. Son instantiation sur les courbes elliptiques a permis le déploiement de primitives asymétriques efficaces sur des systèmes embarqués. Les cryptosystèmes utilisant des courbes elliptiques sont intensément utilisés: il est impératif de savoir estimer précisément la robustesse de ces systèmes. L'existence de méthode pour transférer un problème de logarithme discret elliptique sur une autre courbe algébrique, ainsi que de récents travaux sur l'arithmétique des courbes de genre 2, imposent de ne pas restreindre l'étude des attaques du problème du logarithme discret aux seules courbes elliptiques.

Dans cette optique, cette thèse s'intéresse aux attaques algébriques de type calcul d'indice sur les courbes de genre supérieur à 1. Ces algorithmes se déroulent en deux phases: on se concentrera sur la première, appelée phase de récolte, qui repose sur de nombreuses modélisations algébriques dépendant de la courbe ciblée. Le problème sous-jacent revient à savoir décomposer efficacement des points dans la variété Jacobienne de la courbe en somme d'autres points. On proposera dans un premier temps une approche par crible pour la phase de récolte lorsque des "points lisses" sont recherchés, s'adaptant à tous les types de courbes de genre plus grand que 1. Notre méthode est expérimentalement plus efficace que l'état de l'art.

Ensuite, on étudiera une variante de calcul d'indice appelée attaque par décomposition, ciblant les courbes définies sur des extensions de corps. Dans cette situation, la phase de récolte est effectuée par résolution de systèmes polynomiaux multivariés. On proposera une nouvelle approche de modélisation de ces systèmes, généralisant la notion de polynômes de sommation elliptique à tous les types de courbes algébriques. Cette nouvelle approche sera comparée à l'approche de Nagao dans le cas des courbes hyperelliptiques.

Enfin, on fournira une amélioration théorique et algorithmique du processus de résolution de ces systèmes lorsque le corps de base est de caractéristique 2, tant pour notre nouvelle approche que pour l'approche de Nagao. Par le biais d'une présentation générale et en utilisant des méthodes de bases de Gröbner, on propose une analyse fine de l'impact de ces améliorations sur la complexité de la résolution. Cette analyse fine, ainsi qu'une implémentation dédiée, nous permettent d'estimer le temps de la phase de récolte dans une attaque par décomposition sur une courbe de genre 2 satisfaisant des bornes de sécurité réaliste.

Soutenance : 14/12/2016

Membres du jury :

M. David Lubiz, Responsable scientifique (DGA), Chargé de Recherche (IRMAR, Université Rennes 1) Rapporteur
M. François Morain, Professeur (Ecole Polytechnique) - Rapporteur
M. Jean-Charles Faugère, Directeur de Recherche (INRIA-UPMC-CNRS)
Mme. Vanessa Vitse, Maître de conférence (UJF Grenoble)
M. Stef Graillat, Professeur (UPMC Paris 6)
M. Mohab Safey El Din, Professeur (UPMC Paris 6)

Publications 2015-2018

• 2018
  • J.‑Ch. Faugère, A. Wallet : “The Point Decomposition Problem over Hyperelliptic Curves: toward efficient computations of Discrete Logarithms in even characteristic”, Designs, Codes and Cryptography, vol. 86, pp. 2279–2314, (Springer Verlag) (2018)
• 2016
  • A. Wallet : “Le problème de décomposition de points dans les variétés Jacobiennes”, soutenance de thèse, soutenance 14/12/2016, direction de recherche Faugère, Jean-Charles, co-encadrement : Vitse, Vanessa (2016)
• 2015
  • V. Vitse, A. Wallet : “Improved Sieving on Algebraic Curves”, Progress in Cryptology -- LATINCRYPT 2015, vol. 9230, Lecture Notes in Computer Science, Guadalajara, Mexico, pp. 295-307 (2015)