From Orientations to $\ell$-adic Period Vectors

Titre : Des Orientations aux Vecteurs de Périodes $\ell$-adiques

1. Problématique et Contexte

L'article propose de combler un fossé théorique et pratique entre deux domaines majeurs de la cryptographie post-quantique et de la géométrie arithmétique :

• La cryptographie basée sur les isogénies : Utilisant la structure des graphes d'isogénies de courbes elliptiques supersingulières orientées (comme dans CSIDH, OSIDH, SQISign).
• La géométrie arithmétique des courbes modulaires : Utilisant les symboles modulaires, l'intégration $\ell$-adique (intégrales de Coleman) et la topologie des courbes modulaires $X_0(N)$.

Le problème central est de définir un encodage explicite et calculable qui transforme une courbe elliptique supersingulière orientée (un objet algébrique complexe) en un vecteur de données $\ell$-adiques discret (un objet analytique/combinatoire). Cela ouvre la voie à de nouveaux problèmes de difficulté computationnelle distincts des problèmes d'isogénies classiques ou des problèmes de réseaux (SIS/LWE).

2. Méthodologie

L'auteur développe un pipeline algébrique-analytique en plusieurs étapes pour associer à une orientation de courbe supersingulière un vecteur de périodes tronqué.

A. Orientations et Classes d'Idéaux

• On considère une courbe supersingulière $E$ sur $\mathbb{F}_p$ munie d'une orientation $\iota : \mathcal{O} \hookrightarrow \text{End}(E)$, où $\mathcal{O}$ est un ordre dans un corps quadratique imaginaire $K$.
• L'ensemble de ces courbes orientées est paramétré par le groupe de classes d'idéaux $\text{Pic}(\mathcal{O})$. L'action d'un idéal $\mathfrak{a} \in \text{Pic}(\mathcal{O})$ sur une courbe de base $(E_0, \iota_0)$ produit une nouvelle courbe $(E_{\mathfrak{a}}, \iota_{\mathfrak{a}})$ via une isogénie.

B. Correspondance vers l'Homologie Modulaire
L'auteur propose trois constructions équivalentes (à indice fini près) pour associer une classe d'homologie relative $\gamma(\mathfrak{a}) \in H_1(X_0(N), \mathcal{C}; \mathbb{Z})$ à l'orientation :

1. Module de Brandt : Utilisation de la correspondance de Jacquet-Langlands pour mapper l'action du groupe de classes sur les modules de Brandt (idéaux à gauche d'ordres de quaternion) vers l'homologie de la courbe modulaire.
2. Points de Heegner : Construction géométrique via les points de CM (Multiplication Complexe) sur la courbe analytique $X_0(N)(\mathbb{C})$ et les chemins géodésiques reliant ces points aux pointes (cusps).
3. Arbres de Bruhat-Tits : Utilisation de l'uniformisation de Cerednik-Drinfeld. L'action du groupe de classes sur les courbes orientées correspond à un chemin dans l'arbre de Bruhat-Tits associé à $PGL_2(\mathbb{Q}_\ell)$. Ce chemin est ensuite spécialisé en un cycle d'homologie algébrique.

C. Calcul des Périodes $\ell$-adiques

• Une fois la classe d'homologie $\gamma(\mathfrak{a})$ obtenue, on la couple avec des formes modulaires de poids 2 (cusp forms) $f_1, \dots, f_d$.
• Au lieu d'intégrales complexes, l'article utilise les intégrales de Coleman (intégration $\ell$-adique sur les courbes) pour calculer les périodes :
  $$\langle f_i, \gamma \rangle_\ell \in \mathbb{Q}_\ell$$
• Le vecteur de périodes tronqué est défini par réduction modulo $\ell^m$ :
  $$\Pi_m(\gamma) = (\langle f_1, \gamma \rangle_\ell, \dots, \langle f_d, \gamma \rangle_\ell) \pmod{\ell^m} \in (\mathbb{Z}/\ell^m\mathbb{Z})^d$$
• L'algorithme de Chen-Kedlaya-Lau est mentionné comme méthode efficace pour calculer ces intégrales directement à partir des développements en $q$ des formes modulaires, sans modèle algébrique explicite de la courbe.

3. Contributions Clés

1. Le Pont Algébrique-Analytique : La construction explicite d'un morphisme $\Pi_m$ reliant l'arithmétique des courbes supersingulières orientées (via $\text{Pic}(\mathcal{O})$) à l'homologie relative de la courbe modulaire $X_0(N)$ et aux vecteurs de périodes $\ell$-adiques.
2. Le Problème d'Inversion des Symboles Modulaires (MSI) :
   • Définition : Étant donné un vecteur $y = \Pi_m(\gamma^*)$ où $\gamma^*$ est une classe d'homologie « courte » (représentée par un chemin de longueur bornée $L$ dans une structure combinatoire, comme un arbre de Bruhat-Tits), retrouver n'importe quelle classe courte $\gamma$ telle que $\Pi_m(\gamma) = y$.
   • Nature du problème : C'est un problème de recherche de chemin dans un graphe exponentiellement grand, contraint par des relations linéaires modulo $\ell^m$.
3. Nouveaux Primitifs Cryptographiques :
   • Protocole d'identification : Basé sur la difficulté de l'inversion de $\Pi_m$ (analogie avec les schémas à engagement).
   • Fonctions Pseudo-Aléatoires (PRF) : Construction de PRF où la clé secrète est un chemin court et la sortie est le vecteur de périodes dérivé.

4. Résultats et Analyse de Sécurité

• Complexité Combinatoire : La difficulté du problème MSI repose sur la croissance exponentielle du nombre de chemins valides de longueur $L$ (noté $W_L$) dans le graphe sous-jacent (arbre de Bruhat-Tits ou graphe d'isogénies).
• Comparaison avec SIS/LWE : Bien que la forme $Ax \equiv y \pmod{\ell^m}$ rappelle les problèmes de réseaux (SIS), la contrainte de « chemin valide » rend le vecteur solution extrêmement rare et structuré. Les réductions connues pour SIS/LWE ne s'appliquent pas.
• Comparaison avec les Isogénies : Le problème est conceptuellement proche de la recherche de chemin dans les graphes d'isogénies supersingulières, mais opère dans l'espace d'homologie de la courbe modulaire plutôt que directement sur les courbes elliptiques.
• Résistance Quantique : Les attaques quantiques (comme Grover) ne fournissent qu'une accélération quadratique, laissant la complexité exponentielle en $L$.
• Paramètres : Pour une sécurité de $\lambda$ bits, il faut que $\ell^{md} \gg (\#W_L)^2$ pour éviter les collisions, et que $B^L \gg 2^\lambda$ (où $B$ est le facteur de branchement).

5. Signification et Perspectives

• Nouvelle Hypothèse de Difficulté : L'article introduit le problème MSI comme une hypothèse de sécurité post-quantique distincte, enrichissant le paysage des primitives cryptographiques au-delà des isogénies pures et des réseaux.
• Utilisation des Outils Classiques : Il démontre comment des outils profonds de la théorie des nombres (symboles modulaires, intégrales de Coleman, uniformisation de Cerednik-Drinfeld) peuvent être réutilisés pour concevoir des primitives cryptographiques modernes.
• État de l'Art : Les constructions sont présentées à un stade exploratoire. Les travaux futurs doivent se concentrer sur l'analyse fine des paramètres, l'implémentation efficace des intégrales de Coleman pour des niveaux $N$ élevés, et l'étude des attaques structurelles potentielles contre la contrainte de chemin.

En résumé, ce travail propose une nouvelle voie pour la cryptographie post-quantique en traduisant la complexité combinatoire des graphes d'isogénies orientés en problèmes d'algèbre linéaire sur des périodes $\ell$-adiques, offrant ainsi une alternative prometteuse aux schémas existants.