LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » Actualité » Doctorants
http://www-polsys.lip6.fr/~huot/

HUOT Louise

Docteur
Équipe : PolSys
Date de départ : 31/08/2014
http://www-polsys.lip6.fr/~huot/
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 - 14h - Site Jussieu 25-26/105
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

 Mentions légales
Carte du site |