Description
Date depot: 1 janvier 1900
Titre: Systèmes polynomiaux liés aux attaques du problème du logarithme discret sur les courbes algébriques
Directeur de thèse:
Jean-Charles FAUGÈRE (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Le problème du logarithme discret sur courbes elliptiques (ou plus généralement sur les jacobiennes de courbes algébriques), introduit en cryptologie au milieu des années 80, ne connaît jusqu'à présent pas d'algorithme permettant de l'attaquer vraiment efficacement. Pour cette raison, il est à la base de nombreux protocoles cryptographiques qui supplantent peu à peu le célèbre système RSA, et les propriétés algorithmiques des courbes algébriques définies sur des corps finis est un domaine de recherche très actif, avec plusieurs conférences internationales dédiées chaque année. De plus, ces cryptosystèmes seront d’ici peu les standards industriels de la sécurité informatique, et il est donc essentiel d’estimer précisément les paramètres de sécurité.
Du point de vue de la cryptanalyse, certaines attaques du problème du logarithme discret basées sur des méthodes de calcul d'indices, et s'appuyant sur la résolution de systèmes pour la recherche de relations, sont toutefois prometteuses. Après les travaux précurseurs (Gaudry 2008, Diem 2008), plusieurs percées ont été réalisées récemment dans cette direction, notamment pour les courbes définies sur des extensions de petit degré de corps finis (Joux-Vitse 2012, Faugère-Gaudry-Huot-Renault 2013) ; les courbes définies sur des corps binaires seraient aussi potentiellement vulnérables (Faugère-Petit-Perret-Renault 2012). L'efficacité de toutes ces méthodes repose essentiellement sur la résolution de systèmes polynomiaux dans une première phase (recherche de relations), puis sur la résolution de très gros systèmes linéaires creux dans un deuxième temps. Sur le plan théorique, c'est cette première phase qui est clairement la plus stimulante. En effet, le principal outil utilisé est la résolution de systèmes algébriques par calcul de bases de Gröbner et il est difficile d’en estimer précisément la complexité. Cependant, pour les systèmes intervenant en cryptanalyse algébrique il est parfois possible d'exploiter une structuration particulière pour obtenir de meilleurs résultats (c’est par exemple ce qui a été réalisé pour les systèmes bilinéaires dans Faugère-Safey El Din-Spaenlehauer 2011). L’obtention de bornes précises pourrait permettre d’obtenir un algorithme sous-exponentiel pour résoudre le problème du logarithme discret pour les courbes elliptiques ; ceci a été conjecturé par certains auteurs (Petit-Quisquater 2012). En plus de ces aspects théoriques, l'implantation efficace d'algorithmes spécifiques de résolution est d'une importance pratique capitale afin de valider expérimentalement ces conjectures.
Doctorant.e: Wallet Alexandre