[Offre de thèse] Le problème du logarithme discret pour les corps finis de petites extensions

Contexte et atouts du poste

Contexte : La cryptologie consiste en l’étude des techniques utilisées par deux entités pour communiquer en secret en présence d’une personne adverse. Ces techniques, ou cryptosystèmes, qui détaillent comment chiffrer et déchiffrer les messages, sont conçues autours de problèmes calculatoires réputés difficiles. Les propriétés mathématiques sous-jacentes à ces problèmes garantissent que l’attaque de tels algorithmes reste infaisable en pratique par un adversaire malveillant, même si celui- ci dispose de la totalité de la puissance de calcul informatique de la planète. Ainsi, les protocoles mis en jeu s’appuient sur diverses hypothèses provenant souvent de la théorie des nombres, comme la difficulté présumée de factoriser de grands entiers ou de calculer le logarithme discret d’un élément aléatoire dans certains groupes.

L’objectif de cette thèse est d’évaluer les faiblesses de l’un des problèmes majeurs sur lequel repose la cryptographie à clef publique actuelle : le problème du logarithme discret, ici considéré dans le cas des corps finis de petites extensions. Pour cela, le doctorant devra analyser les différents algorithmes existants pour attaquer ce problème, construire de nouvelles variantes plus performantes en terme pratiques ou de complexité théorique, et valider ses résultats par des implémentations efficaces.

Des déplacements en conférence ou en séminaire, en France comme à l’étranger sont possibles pour ce poste, en fonction de l’évolution des conditions sanitaires locales et dans le monde. Si tel était le cas, les frais de déplacements seront pris en charge dans la limite du barème en vigueur. Egalement en fonction des conditions sanitaires, il est possible qu’une partie de la mission soit assurée en télétravail.

Mission confiée

Missions :
Cette thèse s’articulera autour de plusieurs axes. Il s’agira notamment de prendre en main l’algorithme de crible algébrique (NFS) ainsi que ses différentes variantes. Tous ces algorithmes néanmoins s’articulent autour de plusieurs étapes : sélection polynomiale, crible, algèbre linéaire et reconstruction finale d’un logarithme discret.

Pour les extensions composées, le doctorant ou la doctorante devra s’approprier l’algorithme d’attaque le plus pertinent dans ce contexte, TNFS. Une meilleure compréhension de TNFS est essentielle aujourd’hui, car les estimations de taille de clefs existantes s’appuient sur l’algorithme général (NFS) et ne sont donc vraisemblablement plus adéquates. Par exemple, le corps GF(p^4) avec p un nombre premier de 298 bits apparait naturellement dans certaines propositions, comme les blockchaines. Ces corps qui proviennent de la cryptographie s’appuyant sur les couplages sont nécessaires à l’implémentation des nouveaux protocoles sans divulgation de connaissance (Zk-znark en anglais) indispensables à la rédaction des contracts intelligents (smart contracts). La taille des clefs nous semble cependant alarmant : p^4 est de 1192 bits donc certes bien au delà des records actuels (392 bits attaqués en 2015 pour un corps d’extension 4) mais il est aujourd’hui une cible potentielle pour TNFS.

Dans ce cadre, des pistes différentes et complémentaires seront à explorer. Le crible dans TNFS exige d’énumérer des vecteurs dans des réseaux euclidiens de dimension plus grandes que 4, là où NFS s’arrêtait en dimension 2. Plusieurs idées pour améliorer le crible sont à envisager : étudier des espaces de géométries variées (sphères, pavés, ellipsoïdes…), trouver une alternative à la première étape d’orthogonalisation du réseau etc.

La dernière phase de reconstruction de logarithme individuelle nécessite aussi une adaptation. Des premiers travaux de Guillevic vont en ce sens, et proposent une étape particulièrement adaptée à TNFS. Une piste de recherche prometteuse pour la personne candidate consisterait à combiner celle-ci avec les méthodes usuelles de NFS.

Enfin, l’intégralité des recherches menées ne perdra pas de vue l’objectif de s’attaquer aussi aux corps finis de petites extensions mais non composées. Les variantes adéquates de TNFS ne s’appliquent plus. Il s’agit alors de revenir à NFS, et plus précisément à sa variante multiple : MNFS. Asymptotiquement, MNFS est connu pour être l’algorithme le plus efficace mais son comportement en pratique est encore inconnu. Un axe de cette thèse consistera donc à explorer cette voie. De même, si en théorie la composition des variantes T et M de NFS est possible et donne des résultats optimaux, le comportement d’un tel algorithme hybride reste encore flou pour des tailles concrètes de paramètres. De fortes améliorations sont attendues, lorsque MNFS sera mis en pratique.

Pour une meilleure connaissance du sujet de recherche proposé :

Un état de l’art sur le problème du logarithme discret est disponible ici :

https://members.loria.fr/Cecile.Pierrot/papers/DlogSurvey.pdf

Quelques articles fondateurs qui peuvent être également consultés :

  • L’algorithme TNFS : Razvan Barbulescu, Pierrick Gaudry, et Thorsten Kleinjung. The tower number field sieve. In Tetsu Iwata and Jung Hee Cheon, editors, ASIACRYPT 2015, Part II, volume 9453 of LNCS, pages 31–55. Springer, Heidelberg, November / December 2015.
  • L’algorithme MNFS : Razvan Barbulescu et Cécile Pierrot. The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields. LMS Journal of Computation and Mathematics, 17 : 230– 246, 2014.
  • Une adaption de la reconstruction du logarithme pour TNFS : Aurore Guillevic. Faster individual discrete logarithms in finite fields of composite extension degree. Mathematics of Computation, 88(317) :1273–1301, January 2019.

Collaboration / Encadrement :

La personne recrutée sera sous la direction d’Emmanuel Thomé, Directeur de Recherche, et Cécile Pierrot, Chargée de Recherche. Elle sera pleinement intégrée à CARAMBA, une  équipe de recherche dont les membres s’intéressent à des questions d’algorithmiques liées à la cryptographie. Plus d’informations ici : https://www.inria.fr/equipes/caramba

Enseignement : La personne recrutée pourra postuler pour mener une activité complémentaire d’enseignement sur le site de Nancy (Faculté des Sciences, IUT, École des mines de Nancy…). Cette charge, qui n’est en rien obligatoire, ni garantie, pourra être encadrée par un avenant au contrat doctoral permettant un complément de salaire.

Principales activités

Principales activités :

  • Analyser les différents algorithmes d’énumération de réseau euclidien pour le crible en grande dimension et définir la meilleure stratégie dans le cadre de TNFS.
  • Concevoir des solutions algorithmiques pour la reconstruction de logarithme discret de TNFS.
  • Proposer des paramètres concrets pour l’implémentation de MNFS et réaliser une première attaque pratique avec celui-ci.
  • Etudier la possibilité de combiner MNFS et TNFS en pratique.
  • Propager les avancées obtenues vers la factorisation.

Activités complémentaires :

  • Rédiger les avancées obtenues sous la forme d’articles scientifiques.
  • Présenter ses travaux en conférence devant un public d’experts du domaine.

Compétences

Compétences techniques et niveau requis :

Master 2 (ou équivalent) en Informatique ou Mathématiques

Langues :

Français ou Anglais

Compétences relationnelles :

La personne recrutée sera amenée à communiquer régulièrement avec ses encadrants. Il est attendu qu’elle soit présente quotidiennement au laboratoire (en fonction des conditions sanitaires) et qu’elle s’intègre et participe activement à la vie de l’équipe.

Aucune offre n'est disponible pour l'instant.

Logo d'Inria