[Offre de thèse] Algorithmique des Modules de Drinfeld et Cryptographie Post-Quantique.

Contexte et motivation

Le contexte de ce sujet de thèse est l’algorithmique des isogénies, avec comme application principale la cryptographie à clef publique post-quantique. La sécurité de la plupart des systèmes cryptographiques à clef publique actuellement déployés à grande échelle repose sur la factorisation d’entiers ou le problème du logarithme discret. Cette sécurité est sous la menace de la potentielle apparition d’un ordinateur quantique suffisamment puissant, pour lequel il existerait des algorithmes permettant de casser ces cryptosystèmes.

Bien que les cryptosystèmes classiques assureront encore pendant de nombreuses années la sécurité de nos outils informatiques, il faut se préparer à cette menace technologique en proposant des systèmes résistants aux méthodes quantiques connues. De plus, certaines applications nécessitent des systèmes cryptographiques pour lequels on doit pouvoir avoir confiance en le fait que leur sécurité soit encore suffisante dans  plusieurs dizaines d’années, en dépit d’évolutions technologiques difficilement prédictibles.

Pour ces raisons, la communauté cryptographique s’est tournée vers l’élaboration de cryptosystèmes dits post-quantiques qui consistent en des algorithmes résistants à des attaques menées par un adversaire qui aurait accès à un ordinateur quantique. Ce pan de la cryptographie a pris une importance considérable cette dernière décennie, notamment suite au projet de standardisation mené par le NIST (https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization). Parmi les propositions en lice dans la compétition organisée par le NIST se trouvent des constructions basées sur les isogénies de courbes elliptiques ; ces constructions cryptographiques forment la pierre angulaire de ce sujet de thèse.

Les modules de Drinfeld sont des outils mathématiques introduits par Vladimir Drinfeld en 1974 pour démontrer certains cas particuliers des conjectures de Langlands. Ces outils partagent un grand nombre de propriétés similaires avec les courbes elliptiques, ce qui en font des candidats naturels à examiner pour la construction de cryptosystèmes post-quantiques alternatifs basés sur les isogénies.

La cryptographie basée sur les modules de Drinfeld n’est en réalité pas nouvelle : il y a une vingtaine d’années, des systèmes cryptographiques basés sur les modules de Drinfeld ont vu le jour. Malheureusement, ces systèmes se sont révélés vulnérables à des attaques, ce qui a mis un frein rapide à leur développement. Néanmoins, le fonctionnement de ces cryptosystèmes était très différent des systèmes basés sur les isogénies, et leur faiblesse n’est en rien un obstacle à la conception de systèmes basés sur des isogénies de modules de Drinfeld. Il existe des résultats négatifs récents qui semblent indiquer qu’une tentative directe de transposer mutatis mutandis des systèmes d’échange de clés post-quantiques à base de courbes elliptiques dans le monde des modules de Drinfeld de rang 2 ne permet pas d’atteindre un niveau de sécurité suffisant, car on sait calculer efficacement des isogénies de degré donné entre des modules de Drinfeld sur un corps fini, ce qui est une différence majeure avec le cas des courbes elliptiques. Cependant, le faible nombre de travaux scientifiques sur ce sujet laisse de la place à l’exploration de nouvelles constructions spécifiques aux modules de Drinfeld et à leur analyse : on peut par exemple se poser la question du cas des modules de Drinfeld de rang plus grand que 2 – où l’analogie avec les courbes elliptiques devient moins claire – ou de l’utilisation de protocoles où le degré des isogénies est inconnu, par exemple pour la construction de fonctions de hachage cryptographique ou de Verifiable Delay Functions.

Sujet

On peut identifier plusieurs explications au fait que l’algorithmique des modules de Drinfeld ait reçu nettement moins d’attention que celle des courbes algébriques par la communauté académique. Tout d’abord, l’important succès des cryptosystèmes classiques basés sur les courbes elliptiques a permis à la communauté cryptographique d’avoir à sa disposition et de réutiliser une boîte à outils très fournie de méthodes  algorithmiques. De plus, la théorie des modules de Drinfeld nécessite un bagage théorique conséquent en mathématiques, ce qui rend difficile l’accès à ce sujet de recherche. Un symptôme notable est le peu de code disponible qui implémente des algorithmes pour les modules de Drinfeld.

Enfin, bien que les questions de calcul effectif pour les modules de Drinfeld avaient déjà été abordées dans les années 90, ce n’est que très récemment que les outils de calcul formel modernes ont été mis en oeuvre pour développer des méthodes efficaces pour les modules de Drinfeld, notamment dans le but d’obtenir des algorithmes asymptotiquement rapides pour la factorisation de polynômes univariés. La boîte à outils  algorithmique pour les modules de Drinfeld est pour l’instant peu conséquente, et le travail de cette thèse a vocation à contribuer à son développement.

On peut ainsi définir trois objectifs pour cette thèse :

Objectif 1 : Revisiter des méthodes algorithmiques classiques pour les modules de Drinfeld, à la lumière des développements récents en cryptographie et en calcul formel.

Objectif 2 : Étudier plus précisément l’utilisation de modules de Drinfeld pour la cryptographie basée sur les isogénies. En particulier, on pourra réfléchir à la conception de nouveaux cryptosystèmes, chercher à identifier des problèmes difficiles sur lesquels faire reposer la sécurité, ou encore réfléchir à des preuves de sécurité basées sur des réductions vers d’autres problèmes algorithmiques.

Objectif 3 : Suivre l’évolution des méthodes cryptographiques basées sur les isogénies de courbes elliptiques. Sur ce volet, il est difficile de prévoir quelles seront les développements de ce domaine dans les  prochaines années, et il sera crucial d’être au courant des développements les plus récents.

L’objectif principal de la thèse est l’objectif 2, qui comporte un certain risque : ce sujet ayant été peu étudié jusqu’à présent, il est possible que cela ne débouche pas sur une construction cryptographique suffisamment solide. Si cette piste refroidit, il sera possible sans difficulté de réorienter la thèse soit vers d’autres applications de l’algorithmique des modules de Drinfeld (par exemple, la factorisation de polynômes univariés), soit vers l’étude de cryptosystèmes basés sur les isogénies de courbes elliptiques. En effet, ces domaines partagent un socle commun de connaissances théoriques, de telle sorte qu’une fois que ces compétences seront acquises, il sera assez facile de rediriger la trajectoire scientifique de la thèse si une piste s’avère moins fructueuse que prévu initialement.

Compétences requises ou à acquérir, débouchés

Les compétences nécessaires pour mener à bien ce travail de thèse relèvent des mathématiques et de l’informatique. Du côté mathématique, des outils de géométrie algébrique et de théorie des nombres sont requis : le socle théorique nécessaire pour l’étude des isogénies est très riche, et il sera important d’être à l’aise avec les concepts abstraits qui y interviennent. Du point de vue informatique, des connaissances en algorithmique, en calcul formel et en complexité sont essentielles. Il y a de plus des aspects d’implémentation qui seront importants pour la mise en oeuvre des algorithmes et pour les expérimentations. Par exemple,
l’implémentation efficace de l’arithmétique des polynômes univariés à coefficients dans un petit corps fini – essentielle à l’algorithmique des modules de Drinfeld – nécessite de connaître un certain nombre de
finesses de programmation. Pour finir, une culture générale en cryptographie et en sécurité informatique est importante pour situer le travail dans un contexte plus large.

En termes de débouchés, il y a de nombreuses équipes académiques en mathématiques ou en informatique, en France ou à l’étranger, qui travaillent sur des sujets connexes. La cryptographie basée sur les isogénies est en plein essor, et de plus en plus de chercheurs s’intéressent à ces questions. On peut aussi mentionner les agences gouvernementales comme l’ANSSI, la DGA, la DGSE, qui peuvent être intéressées par un docteur ayant fait sa thèse sur un sujet qui est directement relié aux évolutions les plus récentes de la recherche en cryptographie. Il existe aussi des possibilités du côté industriel, dans des grands groupes ou des PME  intéressés par la cryptographie, par exemple Thalès, Axalto, Idemia, etc.

Cadre d’accueil

Cette thèse sera co-dirigée par Emmanuel Thomé et Pierre-Jean Spaenlehauer. Les deux co-directeurs sont bien placés pour superviser un travail sur l’utilisation d’isogénies en cryptographie. En effet, E. Thomé a récemment co-dirigé une thèse sur les isogénies de courbes elliptiques, et a par ailleurs contribué à l’étude des isogénies pour les courbes de genre 2. P.-J. Spaenlehauer a contribué récemment au sujet du comptage de points de courbes algébriques en co-dirigeant une thèse sur ce sujet : les outils algorithmiques qui apparaissent dans les problématiques liées au comptage de points sont très similaires à ceux utilisés pour les isogénies.

Le travail sera effectué au sein de l’équipe CARAMBA du laboratoire LORIA. Le présent sujet de thèse est au cœur des objectifs généraux de l’équipe, parmi lesquels on trouve également la factorisation d’entiers, le problème du logarithme discret, l’arithmétique efficace, ainsi que divers aspects de cryptographie et de sécurité informatique (cryptographie symétrique, vote électronique, etc.). L’équipe a accès à des clusters de calcul de plusieurs milliers de cœurs, qui pourront être utilisés si nécessaire pour effectuer des calculs records.

Bibliographie

[1] S. Abelard, P. Gaudry, and P.-J. Spaenlehauer. Counting points on genus-3 hyperelliptic curves with explicit real multiplication. The Open Book Series , 2(1) :119, 2019.
[2] S. Abelard, P. Gaudry, and P.-J. Spaenlehauer. Improved complexity bounds for counting points on hyperelliptic curves. Foundations of Computational Mathematics , 19(3) :591621, 2019.
[3] S. R. Blackburn, C. F. A. Cid, and S. D. Galbraith. Cryptanalysis of a cryptosystem based on Drinfeld modules. IEE Proceedings – Information Security , 153(1) :1214, 2006.
[4] J. Doliskani, A. K. Narayanan, and É. Schost. Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields. Journal of Symbolic Computation , 2020.
[5] V. Drinfeld. Elliptic modules. Mathematics of the USSR-Sbornik , 23(4) :561, 1974.
[6] D. Dummit and D. Hayes. Rank-one Drinfeld modules on elliptic curves. Mathematics of Computation, 62(206) :875883, 1994.
[7] R. Gillard, F. Leprevost, A. Panchishkin, and X.-F. Roblot. Utilisation des modules de Drinfeld en cryptologie. CR Acad. Sci. Paris, Ser. I , 336(11) :879882, 2003.
[8] S. Ionica and E. Thomé. Isogeny graphs with maximal real multiplication. Journal of Number Theory, 207 :385422, 2020.
[9] A. Joux and A. K. Narayanan. Drinfeld modules may not be for isogeny-based cryptography, 2019. Preprint. https://eprint.iacr.org/2019/1329 .
[10] Y. Musleh and É. Schost. Computing the characteristic polynomial of a finite rank two Drinfeld module. In Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation , pages
307314, 2019.

Logo d'Inria