Contract type : Fixed-term contract
Level of qualifications required : Graduate degree or equivalent
Fonction : PhD Position
Context
Équipe
Équipe-projet CARAMBA, Centre Inria Nancy - Grand Est.
Contacts
- Pierre-Jean Spaenlehauer, pierre-jean.spaenlehauer@inria.fr
- Pierrick Gaudry, pierrick.gaudry@loria.fr
Assignment
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.
Main activities
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.
Skills
Required qualifications
MSc in computer science / computational mathematics.
Language
French or English.
Benefits package
- 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
Remuneration
2051€ brut/mois pour la 1ère et la 2ème année. 2158€ brut/mois pour la 3ème année.
Share
General Information
- Theme/Domain :
Algorithmics, Computer Algebra and Cryptology
Scientific computing (BAP E) - Town/city : Villers lès Nancy
- Inria Center : CRI Nancy - Grand Est
- Starting date : 2023-10-01
- Duration of contract : 3 years
- Deadline to apply : 2023-06-30
Contacts
- Inria Team : CARAMBA
-
PhD Supervisor :
Spaenlehauer Pierre Jean / pierre-jean.spaenlehauer@inria.fr
The keys to success
Application deadline
June 30th, 2023 (Midnight Paris time)
How to apply
Upload your file on jobs.inria.fr in a single pdf or zip file, and send it as well by email to pierrick.gaudry@loria.fr and pierre-jean.spaenlehauer@inria.fr. Your file should contain the following documents:
- Your CV.
- A cover/motivation letter describing your interest in this topic.
- A short (max one page) description of your Master thesis (or equivalent) or of the work in progress if not yet completed.
- Your degree certificates and transcripts for Bachelor and Master (or the last 5 years).
- Master thesis (or equivalent) if it is already completed and publications if any(it is not expected that you have any). Only the web links to these documentsare preferable, if possible.
In addition, one recommendation letter from the person who supervises(d) your Master thesis (or research project or internship) should be sent directly by his/her author to pierrick.gaudry@loria.fr and pierre-jean.spaenlehauer@inria.fr.
Applications are to be sent as soon as possible.
About Inria
Inria is the French national research institute dedicated to digital science and technology. It employs 2,600 people. Its 200 agile project teams, generally run jointly with academic partners, include more than 3,500 scientists and engineers working to meet the challenges of digital technology, often at the interface with other disciplines. The Institute also employs numerous talents in over forty different professions. 900 research support staff contribute to the preparation and development of scientific and entrepreneurial projects that have a worldwide impact.
Instruction to apply
Defence Security :
This position is likely to be situated in a restricted area (ZRR), as defined in Decree No. 2011-1425 relating to the protection of national scientific and technical potential (PPST).Authorisation to enter an area is granted by the director of the unit, following a favourable Ministerial decision, as defined in the decree of 3 July 2012 relating to the PPST. An unfavourable Ministerial decision in respect of a position situated in a ZRR would result in the cancellation of the appointment.
Recruitment Policy :
As part of its diversity policy, all Inria positions are accessible to people with disabilities.
Warning : you must enter your e-mail address in order to save your application to Inria. Applications must be submitted online on the Inria website. Processing of applications sent from other channels is not guaranteed.