Antoine Leudière

All my talks

Invited talks

Modules de Drinfeld : Action de groupe de classe explicite et implémentation

Details
Where? IRMAR, Géométrie et algèbre effectives seminar (Rennes)
When? 2022 September 23
Slides: presentation handout
Summary

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

Details
Where? INRIA LFANT seminar (Bordeaux)
When? 2022 June 14
Slides: presentation handout
Summary

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

Details
Where? INRIA GRACE seminar (Saclay)
When? 2022 May 30
Slides: presentation handout
Summary

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.

Notes
See the presentation from the INRIA LFANT (2022-06-14) instead.

Conferences

Function field analogue of the CRS key exchange

Details
Where? Journées C2 (Hendaye)
When? 2022 April 19
Slides: presentation handout
Summary

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 (\url{https://csrc.nist.gov/projects/post-quantum-cryptography/}). 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 (\cite{crs-couveignes}, \cite{crs-russes}) et CSIDH (\cite{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 $\overline{\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

Details
Where? JNCF (Marseille)
When? 2022 February 28
Slides: presentation handout
Summary

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.

Notes
See the presentation from the Journées C2 (2022-04-19) instead.