Courbes elliptiques supersingulières orientées et actions de groupe de classe

Thèse en préparation à Aix-Marseille , dans le cadre de Mathématiques et informatique de Marseille (184), en partenariat avec l’Institut de Mathématiques de Marseille (groupe AGLR, équipe de recherche Arithmétique et Théorie de l’Information) depuis le 13-09-2018.

Membres du jury :

Reviewers
– Tanja LANGE, Technische Universiteit Eindhoven (NL)
– Felipe VOLOCH, University of Canterbury (NZ)
Examiners
– Samuele ANNI, Aix-Marseille Université (FR)
– Jean-Marc COUVEIGNES, Institut de mathématiques de Bordeaux (FR)
– Luca DE FEO, IBM Research (CH)
– Elisa LORENZO GARCíA, Université de Neuchâtel (CH)
– Christophe RITZENTHALER, Université de Rennes 1 (FR)
Thesis director
– David KOHEL, Aix-Marseille Université (FR)

Résumé : Cette thèse s’articule autour de divers aspects des courbes elliptiques supersingulières, de leurs anneaux des endomorphismes et des graphes d’isogénies associés. La structure riche de ces graphes en fait un outil important pour aborder plusieurs problèmes en théorie des nombres. Dans ce document, nous étudions différentes facettes et propriétés des graphes d’isogénies supersingulières et nous exploitons leurs nouvelles applications cryptographiques. En particulier, nous décrivons les outils théoriques nécessaires pour orienter les graphes d’isogénies et caractériser leur structure. Nous introduisons une nouvelle catégorie de courbes elliptiques supersingulières orientées, au moyen d’un plongement d’un ordre d’un corps de nombres quadratique imaginaire dans l’anneau d’endomorphismes d’une courbes elliptique supersingulière, et nous obtenons les propriétés du graphe d’isogénie associé. Nous établissons un modèle de calcul qui permet de décrire une action d’un groupe de classes compatible sur ces objets et nous fournissons la description théorique et pratique de la façon dont cette action fonctionne sur les courbes, les chaînes d’isogénies et tout le graphe orienté. Comme application, nous introduisons un protocole d’échange de clés de Diffie et Hellman à base d’isogénies supersingulières orientées (OSIDH), analogue au protocole Diffie et Hellman supersingulier (SIDH) et qui généralise le protocole CSIDH.
En parallèle, nous développons la version modulaire de notre construction. Nous montrons que l’action de groupe peut être effectuée efficacement sur les séquences de points de moduli sur une courbe modulaire uniquement et qu’elle est plus susceptible d’être accéléré en imposant une structure de niveau appropriée. Dans cette direction, nous décrivons une famille de courbes modulaires efficace pour la mise en œuvre de ces idées et nous calculons les propriétés du graphe d’isogénies correspondant, à la fois orienté et non-orienté. Enfin, en utilisant des courbes modulaires avec structure de niveau, nous généralisons l’approche modulaire au protocole OSIDH et nous améliorons sa complexité.

Mots clés : Cryptographie, Isogénie, Diffie-Hellman.

Oriented supersingular elliptic curves and class group actions

Abstract: This thesis revolves around various aspects of supersingular elliptic curves, their endomorphism rings and associated isogeny graphs. The rich structure of these graphs makes them an important implement for approaching several computational problems in number theory. In this document, we study different facets and properties of supersingular isogeny graphs and exploit their potential new cryptographic applications. In particular, we describe the theoretical tools necessary to orient isogeny graphs and characterize their structure. By means of embeddings of quadratic orders in the endomorphism ring of supersingular elliptic curves, we introduce a new category of oriented elliptic curves and derive properties of the associated isogeny graphs. We establish a computational model which permits one to describe a compatible class group action on these objects and provide the theoretical and practical description of how this action works on curves, chains of isogenies and the entire oriented graph. As an application, we introduce an oriented supersingular isogeny Diffie-Hellman protocol (OSIDH), analogous to the supersingular isogeny Diffie-Hellman (SIDH) protocol and generalizing the commutative supersingular isogeny Diffie-Hellman (CSIDH) protocol.
In parallel, we develop an explicit modular version of our construction. We show that the group action can be carried out effectively solely on the sequences of moduli points on a modular curve and is further amenable to speedup by imposing a suitable level structure. In this direction, we describe a suitable family of modular curves and derive the properties of the corresponding covering isogeny graphs, both oriented and non-oriented. Finally, by introducing the use of modular curves of higher level, we expand and improve the complexity of the modular approach to the OSIDH protocol.

Keywords: Cryptography, Isogeny, Diffie-Hellman.

Liens :
https://www.theses.fr/s223262
https://college-doctoral.univ-amu.fr/inscrit/10902
https://adum.parisnanterre.fr/as/ed/cv.pl?mat=100102&site=adumR
https://hal.archives-ouvertes.fr/hal-03089563
https://www.researchgate.net/profile/Leonardo-Colo