Direction de recherche : Jean-Charles FAUGÈRE
Co-encadrement : RENAULT Guénaël, GAUDRY Pierrick

Résolution de systèmes polynomiaux et cryptologie sur les courbes elliptiques

Depuis ces dix dernières années, les attaques sur le logarithme discret sur les courbes elliptiques (ECDLP) mettant en jeu la résolution de systèmes polynomiaux connaissent un large succès. C'est dans ce contexte que s'inscrit cette thèse dont les contributions sont doubles.

D'une part, nous présentons de nouveaux outils de résolution de systèmes polynomiaux par bases de Gröbner. Nous montrons que la résolution de systèmes avec symétries est étroitement liée à la résolution de systèmes quasi-homogènes. Nous proposons ainsi de nouveaux résultats de complexité pour la résolution de tels systèmes. Nous nous intéressons également à l'étape bloquante de la résolution de systèmes : le changement d'ordre pour bases de Gröbner. La complexité classique de cette étape est cubique en le nombre de solutions et domine la complexité totale de la résolution. Nous proposons pour la première fois des algorithmes de changement d'ordre de complexité sous-cubique en le nombre de solutions.

D'autre part, nous nous intéressons à l'attaque du logarithme discret sur les courbes elliptiques par calcul d'indice proposée par Gaudry. Nous mettons en évidence des familles de courbes elliptiques possédant des symétries particulières. Ces symétries impliquent un gain exponentiel sur la complexité de la résolution du ECDLP. Nous obtenons ainsi de nouveaux paramètres de sécurité pour certaines instances du ECDLP. Une des étapes principales de cette attaque nécessite le calcul de polynômes de sommation introduits par Semaev. Les symétries des courbes elliptiques binaires nous permettent d'élaborer un nouvel algorithme par évaluation-interpolation pour le calcul des polynômes de sommation. Munis de cet algorithme nous établissons un nouveau record pour le calcul de ces polynômes.

Soutenance : 13/12/2013

Membres du jury :

M. Reynald Lercier (Chercheur associé IRMAR, Ingénieur DGA MI) [Rapporteur]
M. Éric Schost (Associate Professor University of Western Ontario) [Rapporteur]
M. Jean-Charles Faugère (DR INRIA Paris-Rocquencourt)
M. Pierrick Gaudry (DR CNRS)
M. Antoine Joux (Titulaire de la Chaire de Cryptologie de la fondation partenariale de l'UPMC)
M. Guénaël Renault (Maître de Conférences UPMC)
M. Mohab Safey El Din (Professeur UPMC)
M. Benjamin Smith (CR INRIA Saclay-Île-de-France)

Publications 2012-2014

• 2014
  • J.‑Ch. Faugère, P. Gaudry, L. Huot, G. Renault : “Sub-cubic Change of Ordering for Gröner Basis: A Probabilistic Approach”, ISSAC '14 - Proceedings of the 39^th International Symposium on Symbolic and Algebraic Computation, Kobe, Japan, pp. 170-177, (ACM) (2014)
  • J.‑Ch. Faugère, L. Huot, A. Joux, G. Renault, V. Vitse : “Symmetrized summation polynomials: using small order torsion points to speed up elliptic curve index calculus”, EUROCRYPT 2014 - 33^rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, vol. 8441, Lecture Notes in Computer Science, Copenhagen, Denmark, pp. 40-57, (Springer) (2014)
• 2013
  • L. Huot : “Polynomial systems solving and elliptic curve cryptography”, soutenance de thèse, soutenance 13/12/2013, direction de recherche Faugère, Jean-Charles, co-encadrement : Renault, Guénaël, Gaudry, Pierrick (2013)
  • J.‑Ch. Faugère, P. Gaudry, L. Huot, G. Renault : “Using Symmetries in the Index Calculus for Elliptic Curves Discrete Logarithm”, Journal of Cryptology, pp. 1-40, (Springer Verlag) (2013)
  • J.‑Ch. Faugère, P. Gaudry, L. Huot, G. Renault : “Polynomial Systems Solving by Fast Linear Algebra”, (2013)
• 2012
  • J.‑Ch. Faugère, P. Gaudry, L. Huot, G. Renault : “Using Symmetries and Fast Change of Ordering in the Index Calculus for Elliptic Curves Discrete Logarithm”, SCC 2012 - Third international conference on Symbolic Computation and Cryptography, Castro Urdiales, Spain, pp. 113-118 (2012)