Conference talks
-
Drinfeld modules in SageMath
ISSAC'23 (Tromsø) · 2023-07-26 · presentation handout Abstract
Support presentation for the Software Presentation entitled Drinfeld modules in SageMath accepted at ISSAC'23 (arXiv link).
-
Drinfeld modules in SageMath
Journée du Département 1 du Loria (Nancy) · 2023-04-07 · presentation handout Abstract
Drinfeld modules are mathematical objects that were introduced in the 1970s to answer profound questions in algebra, particularly in the context of the class field theory for function fields. Over time, the theory of Drinfeld modules has become well-established and is now recognized as an essential tool in various significant areas of Mathematics, such as the Langlands program. Notably, Laurent Lafforgue, who used Drinfeld modules to solve open problems from the Langlands program for function fields, was awarded with the Fields Medal in 2002.
Prior to our contribution, Drinfeld modules were absent from all standard distributions of computer algebra systems. We decided to implement Drinfeld modules in SageMath - a popular free and open source computer algebra system. Our implementation is available in the standard distribution of SageMath since version 10.0.
In this presentation, we will review of the development process, with a focus on the crucial issue of data representation. We will see that Drinfeld modules do not directly fit the SageMath paradigm of object representation. Our primary task was thus to to find the best compromise between ecosystem integration, mathematical satisfaction, and interface elegance.
-
Function field analogue of the CRS key exchange
Journées C2 (Hendaye) · 2022-04-19 · presentation handout Abstract
La cryptographie post-quantique naît de la nécessité de se prémunir — avec des ordinateurs classiques — des attaques menées par des ordinateurs quantiques. Cette discipline est particulièrement florissante depuis l’ouverture en 2017 de la compétition de standardisation du NIST. Plusieurs classes de solutions sont en compétition : cryptographie multivariée, des réseaux, des codes correcteurs, ou encore, des isogénies de courbes elliptiques. C’est cette dernière qui nous intéresse, notamment les protocoles d’échange de clé basés sur une action de groupe simplement transitive facile à calculer et difficile à inverser.
Une isogénie de courbes elliptiques est un morphisme (au sens de la géométrie algébrique) de courbes elliptiques qui est aussi un morphisme de groupes. Les cryptosystèmes basés sur ces dernières misent en général sur la difficulté de trouver une isogénie entre deux courbes elliptiques isogènes données, citons CRS (Couveignes et Rostovtsev-Stolbunov et CSIDH. Dans ce paradigme, les clés sont de tailles relativement courte. Néanmoins, les performances de CRS sont peu compétitives ; quant à CSIDH, il est difficile sur un ordinateur classique de calculer la structure du groupe considéré. Dans ce contexte, il est naturel de chercher à adapter ces constructions à d’autres objets mathématiques.
C’est ici que les modules de Drinfeld entrent en jeu. Un module de Drinfeld est une construction algébrique issue de l’arithmétique des corps de fonctions. Ces objets ont des propriétés algébriques extraordinairement proches de celles des courbes elliptiques, à ceci près qu’un module de Drinfeld induit une loi de Fq[X]-module sur la clôture algébrique Fq et non de Z-module sur les points de la courbe elliptique.
Nous proposons un nouveau protocole d’échange de clé, non-interactif, basé sur une action de groupe simplement transitive, facile à calculer et difficile à inverser. La construction, que nous décrirons dans cet exposé, mime celles de CRS et permet de déterminer l’ordre du groupe considéré en temps polynomial. Nous nous intéresserons aussi au problème mathématique sur lequel repose la sécurité du protocole. Nous évoquerons enfin des résultats expérimentaux qui suggèrent que le calcul de l’action de groupe est compétitif avec CSIDH.
-
Hard Homogeneous Spaces from the Class Field Theory of Imaginary Hyperelliptic Function Fields
JNCF (Marseille) · 2022-02-28 · presentation handout Abstract
L’un des objets centraux de la théorie du corps de classes des corps de fonctions est l’action de la jacobienne d’une courbe algébrique sur un sous-ensemble de classes d’isomorphismes de modules de Drinfeld. Dans ce travail, nous nous focalisons sur le cas hyperelliptique et proposons un algorithme efficace pour le calcul de cette action.
Nous verrons que les modules de Drinfeld jouent le rôle d’analogues des courbes elliptiques pour les corps de fonctions, spécialement par leur théorie de la multiplication complexe. L’étude de cette action est motivée par le protocole d’échange de clé de Couveignes-Rostovtsev-Stolbunov (CRS). Nos modules de Drinfeld et corps de fonctions sont alors à voir comme les alternatives dans CRS des courbes elliptiques et corps de nombres.
Des expérimentations numériques suggèrent qu’inverser l’action est un problème difficile. Cette construction pourrait de fait constituer un candidat crédible pour faire de l’échange de clé post-quantique.
Invited talks
-
Modules de Drinfeld : Action de groupe de classe explicite et implémentation
IRMAR, Géométrie et algèbre effectives seminar (Rennes) · 2022-09-23 · presentation handout Abstract
Motivés par la cryptographie des isogénies, nous parlerons de l’algorithmique des modules de Drinfeld et leurs isogénies.
Les modules de Drinfeld ont été introduits dans les années 1970 pour construire une théorie du corps de classe des corps de fonctions explicite, comme celle-ci peut l’être pour les corps de nombres : le corps de classes de Hilbert d’un corps quadratique imaginaire est engendré par les j-invariants des courbes elliptiques ayant multiplication complexe dans ce corps. En ce sens, la théorie modules de Drinfeld fournit un « analogue corps de fonctions » des courbes elliptiques.
Nous décrirons un algorithme simple et court pour le calcul de l’action simplement transitive du groupe de Picard d’une courbe hyperelliptique imaginaire sur un ensemble de classes d’isomorphismes de modules de Drinfeld.
Dans un second temps, nous ferons une démonstration en direct du futur module SageMath pour les modules de Drinfeld, dont nous terminons le développement.
Travail commun avec Pierre-Jean Spaenlehauer.
-
An explicit CRS-like action with Drinfeld modules
INRIA LFANT seminar (Bordeaux) · 2022-06-14 · presentation handout Abstract
L’une des pierres angulaires de la cryptographie des isogénies est l’action (dite CRS), simplement transitive, du groupe des classes d’un ordre d’un corps quadratique imaginaire, sur un certain ensemble de classes d’isomorphismes de courbes elliptiques ordinaires.
L’échange de clé non-interactif basé sur cette action (espace homogène difficile) est relativement lent (de Feo, Kieffer, Smith, 2019) ; la structure du groupe (Beullens, Kleinjung, Vercauteren, 2019) est difficile à calculer. Pour palier à cela, nous décrivons une action, simplement transitive, de la jacobienne d’une courbe hyperelliptique imaginaire, sur un certain ensemble de classes d’isomorphismes de modules de Drinfeld.
Après avoir motivé l’utilisation des modules de Drinfeld en lieu et place des courbes elliptiques, nous décrirons un algorithme efficace de calcul de l’action, ainsi que la récente attaque de Benjamin Wesolowski sur l’échange de clé donné par l’action.
-
An explicit CRS-like action with Drinfeld modules
INRIA GRACE seminar (Saclay) · 2022-05-30 · presentation handout Abstract
L’une des pierres angulaires de la cryptographie des isogénies est l’action (dite CRS), simplement transitive, du groupe des classes d’un ordre d’un corps quadratique imaginaire, sur un certain ensemble de classes d’isomorphismes de courbes elliptiques ordinaires.
L’échange de clé non-interactif basé sur cette action est relativement lent (de Feo, Kieffer, Smith, 2019) ; la structure du groupe sous-jacent (Beullens, Kleinjung, Vercauteren, 2019) est particulièrement difficile à calculer. Cela nous incite à adapter cette construction à d’autres objets mathématiques. Dans ce contexte, nous décrivons une action, simplement transitive, de la jacobienne d’une courbe hyperelliptique imaginaire, sur un certain ensemble de classes d’isomorphismes de modules de Drinfeld.
Nous allons nous convaincre de la pertinence d’utiliser des modules de Drinfeld en lieu et place des courbes elliptiques. Cela fait, nous décrirons certaines propriétés de ces objets, puis notre action de groupe. L’accent sera mis sur son calcul effectif. Sera enfin évoquée la difficulté algorithmique de casser le protocole associé à cette construction ; nous esquisserons la récente attaque de Wesolowski.
