Équipe

Équipe-projet CARAMBA, Centre Inria Nancy - Grand Est.

Contacts

• Pierre-Jean Spaenlehauer, pierre-jean.spaenlehauer@inria.fr
• Pierrick Gaudry, pierrick.gaudry@loria.fr

Contexte, motivation

La cryptographie basée sur les isogénies a connu un développement rapide durant ces dernières années, sous l'impulsion de l'invention en 2011 de SIDH [10], un système d'échange de clé basé sur les isogénies de courbes elliptiques supersingulières. Ce cryptosystème et ses variantes ont connu un fort engouement, notamment dû au fait qu'il promettait de résister aux attaques utilisant un ordinateur quantique. Malheureusement, des travaux récents ont permis de mettre en oeuvre des attaques dévastatrices sur SIDH, le rendant de fait obsolète [3,13]. Toutefois, le mouvement créé par SIDH a permis le développement d'une boîte à outils algorithmique diversifiée pour les isogénies de courbes elliptiques et a conduit également à la découverte d'autres constructions cryptographiques telles que CSIDH [5], SQISign [7], CSI-FiSh [2], etc.

Les faiblesses découvertes récemment montrent l'importance d'étudier des variantes qui peuvent se révéler résistantes aux attaques trouvées sur les systèmes les plus regardés. Une alternative consiste à étudier si les isogénies de variétés abéliennes peuvent servir de substitution aux isogénies de courbes elliptiques. Ceci est notamment motivé par le fait que les isogénies de courbes elliptiques sont des réalisations concrètes de la théorie de la multiplication complexe et de la théorie du corps de classes des corps quadratiques imaginaires, et elles permettent d'adopter un point de vue algorithmique sur ces théories. Ces concepts se généralisent partiellement aux variétés abéliennes via la théorie des corps CM. Des travaux récents [4,6,8] ont commencé à étudier ce qu'il était possible de faire avec ces objets, mais cette ligne de recherche a encore été assez peu explorée.

Sujet et objectifs

Les objets mathématiques qui sont au coeur des attaques récentes sur SIDH sont des variétés abéliennes qui sont isogènes à une  puissance E^n d'une courbe elliptique à multiplication complexe. Ces variétés abéliennes ont été notamment étudié par Kani dans les années 90 [11,12] et ont peu servi en cryptographie avant leur récente entrée fracassante en 2022 dans le contexte des attaques sur SIDH, où ces objets jouent un rôle majeur. Cette sous-catégorie de variétés abéliennes peut être vue comme une famille d'objets intermédiaires entre les courbes elliptiques - où l'algorithmique est très rapide - et les variétés abéliennes générales de dimension > 1, où l'algorithmique rapide demande des outils très sophistiqués qui sont bien moins développés que leurs équivalents en dimension 1.

Un des objectifs de la thèse sera d'étudier ces objets et l'algorithmique de leurs isogénies. On pourra notamment chercher à  développer des outils efficaces pour le calcul effectif de leurs isogénies. Du point de vue des applications cryptographiques, on pourra étudier si le développement de cette boîte à outils algorithmique permet d'analyser les contre-mesures récentes proposées pour parer les attaques sur SIDH [9]. D'un point de vue constructif, il sera également naturel de se demander si ces objets peuvent servir à la conception de protocoles cryptographiques.

Un deuxième objectif de cette thèse sera de faire un état des lieux de la cryptographie basée sur les isogénies de variétés abéliennes de dimension 2 et plus. Le but sera d'étudier si des variantes de protocoles cryptographiques post-quantiques sur les courbes elliptiques peuvent se généraliser à ce contexte. Cet objectif est probablement très ambitieux, et on peut s'attendre à rencontrer de nombreux obstacles pratiques et algorithmiques sur le chemin qui mène à sa réalisation. Cette thèse permettra d'identifier ces obstacles, et de proposer des solutions pour en surmonter. Par conséquent, la thèse pourra provisoirement bifurquer vers le développement d'outils algorithmiques pour les variétés abéliennes, avec une coloration de calcul formel et de géométrie arithmétique effective. Les applications à la cryptographie serviront de boussole pour guider la direction générale que prendra la thèse.

Un troisième objectif général de la thèse sera de contribuer au développement de la boîte à outils pratique de l'algorithmique des isogénies des variétés abéliennes, notamment via des implémentations des algorithmes étudiés.

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 d'arithmétique sont requises ; en particulier lorsque l'on s'oriente vers les calculs explicites d'isogénies, la machinerie utilisée s'enrichit rapidement. L'algèbre commutative et ses aspects effectifs sont aussi des outils omniprésents. Du point de vue informatique, des connaissances en algorithmique, en calcul formel et en complexité sont cruciales. Il y a de plus des aspects d'implémentation et de gestion de gros calculs qui ne sont pas à négliger. Pour finir, une culture générale en cryptographie et en sécurité informatique est importante pour resituer le travail dans un contexte plus large.

En termes de débouchés, il y a bien sûr de nombreuses équipes académiques, en France ou à l'étranger, en mathématiques ou en informatique qui travaillent sur des sujets connexes. On peut aussi mentionner les agences gouvernementales comme l'ANSSI, la DGA, voire la DGSE, comme des points de chute possibles après la thèse. Il existe aussi de sérieuses possibilités du côté industriel, dans des grands groupes ou des PME intéressés par la cryptographie.

Cadre d'accueil

Les deux co-encadrants sont bien placés pour superviser un travail de thèse sur les isogénies. En effet, P. Gaudry et P.-J. Spaenlehauer ont précédemment co-dirigé la thèse de Simon Abelard sur le thème du comptage de points pour les courbes hyperelliptiques, un sujet dont les outils mathématiques sont très proches de ceux de l'algorithmique des isogénies [1]. P.-J. Spaenlehauer co-dirige en ce moment la thèse d'Antoine Leudière dont une partie traite des isogénies de modules de Drinfeld.

Le travail sera effectué au sein de l'équipe CARAMBA du laboratoire LORIA. Le présent sujet de thèse se situe dans les 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 de nombreux aspects de cryptographie asymétrique et symétrique.

Si le travail de thèse prend la direction de la réalisation d'un calcul record (par exemple pour faire une preuve de concept d'un algorithme efficace), l'équipe dispose de machines bien adaptées à ce type de calculs intensifs sur des objets algébriques.

Bibliographie

[1] S. Abelard. Comptage de points de courbes hyperelliptiques en grande caractéristique : algorithmes et complexité. Thèse de doctorat, Université de Lorraine, Sept. 2018.

[2] W. Beullens, T. Kleinjung, and F. Vercauteren. CSI-FiSh : Efficient isogeny based signatures through class group computations. In Advances in Cryptology – ASIACRYPT 2019, pages 227–247, 2019.

[3] W. Castryck and T. Decru. An efficient key recovery attack on SIDH. In Advances in Cryptology – EUROCRYPT 2023, pages 423–447, 2023.

[4] W. Castryck, T. Decru, and B. Smith. Hash functions from superspecial genus-2 curves using Richelot isogenies. Journal of Mathematical Cryptology, 14(1) :268–292, 2020.

[5] W. Castryck, T. Lange, C. Martindale, L. Panny, and J. Renes. CSIDH : An efficient post-quantum commutative group action. In Advances in Cryptology – ASIACRYPT 2018, pages 395–427, 2018.

[6] C. Costello and B. Smith. The supersingular isogeny problem in genus 2 and beyond. In Post-Quantum Cryptography, pages 151–168, 2020.

[7] L. De Feo, D. Kohel, A. Leroux, C. Petit, and B. Wesolowski. SQISign : Compact post-quantum signatures from quaternions and isogenies. In Advances in Cryptology – ASIACRYPT 2020, pages 64–93, 2020.

[8] E. V. Flynn and Y. B. Ti. Genus two isogeny cryptography. In Post-Quantum Cryptography, pages 286–306, 2019.

[9] T. B. Fouotsa, T. Moriya, and C. Petit. M-SIDH and MD-SIDH : Countering SIDH attacks by masking information. In Advances in Cryptology – EUROCRYPT 2023, pages 282–309, 2023.

[10] D. Jao and L. De Feo. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In Post-Quantum Cryptography, pages 19–34, 2011.

[11] E. Kani. The number of curves of genus two with elliptic differentials. Journal für die reine und angewandte Mathematik (Crelles Journal), 1997(485) :93–122, Apr. 1997.

[12] E. Kani. Products of CM elliptic curves. Collectanea mathematica, 62(3) :297–339, Sept. 2011.

[13] D. Robert. Breaking SIDH in polynomial time. In Advances in Cryptology – EUROCRYPT 2023, pages 472–503, 2023.

Required qualifications

MSc in computer science / computational mathematics.

Language

French or English.

• Restauration subventionnée
• Transports publics remboursés partiellement
• Congés: 7 semaines de congés annuels + 10 jours de RTT (base temps plein) + possibilité d'autorisations d'absence exceptionnelle (ex : enfants malades, déménagement)
• Possibilité de télétravail (après 6 mois d'ancienneté) et aménagement du temps de travail
• Équipements professionnels à disposition (visioconférence, prêts de matériels informatiques, etc.)
• Prestations sociales, culturelles et sportives (Association de gestion des œuvres sociales d'Inria)
• Accès à la formation professionnelle
• Sécurité sociale

2051€ brut/mois pour la 1ère et la 2ème année. 2158€ brut/mois pour la 3ème année.