Polynomial systems solving and elliptic curve cryptography

Louise Huot 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Résumé : 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.
Type de document :
Thèse
Symbolic Computation [cs.SC]. Université Pierre et Marie Curie - Paris VI, 2013. English
Liste complète des métadonnées


https://tel.archives-ouvertes.fr/tel-00925271
Contributeur : Louise Huot <>
Soumis le : mardi 7 janvier 2014 - 18:00:12
Dernière modification le : mardi 30 mai 2017 - 01:12:08
Document(s) archivé(s) le : mardi 8 avril 2014 - 00:15:18

Fichier

Identifiants

  • HAL Id : tel-00925271, version 1

Collections

Citation

Louise Huot. Polynomial systems solving and elliptic curve cryptography. Symbolic Computation [cs.SC]. Université Pierre et Marie Curie - Paris VI, 2013. English. <tel-00925271>

Partager

Métriques

Consultations de
la notice

407

Téléchargements du document

605