CSIDH : isogénies supersingulières commutatives

CSIDH (Commutative Supersingular Isogeny Diffie-Hellman, Castryck et al., 2018) est un échange de clés fondé sur les isogénies qui évite entièrement la fuite d’informations sur les points de torsion de SIDH, en utilisant une structure algébrique fondamentalement différente. CSIDH travaille avec des courbes supersingulières sur Fp (et non sur Fp2 comme SIDH). L’hypothèse de difficulté repose sur la commutativité de l’action du groupe des classes : deux parties appliquent chacune un élément secret du groupe des classes à une même courbe de départ, et la commutativité garantit qu’elles parviennent toutes deux à la même courbe partagée. Aucune information auxiliaire sur les points de torsion n’est publiée ; la clé publique est simplement un invariant j unique. Cette conception a résisté à l’attaque de Castryck-Decru contre SIDH.

Sur Fp avec p = 3 mod 4, les courbes supersingulières E possèdent un endomorphisme distingué pi (le Frobenius), et leur algèbre des endomorphismes contient l’ordre quadratique imaginaire Z[pi]. Le groupe des classes d’idéaux Cl(Z[pi]) agit librement et transitivement sur l’ensemble des courbes supersingulières sur Fp, à isomorphisme près. Un idéal a de Cl(Z[pi]) agit sur une courbe E pour produire une nouvelle courbe a * E, calculée comme la courbe E/E[a], où E[a] est le sous-groupe de torsion correspondant à l’idéal a. Cette action est commutative : a * (b * E) = b * (a * E) = [ab] * E. Il s’agit de l’action du groupe CSIDH, qui fournit un analogue commutatif de Diffie-Hellman.

L’échange de clés CSIDH se déroule comme suit. Paramètres publics : une courbe supersingulière E0 sur Fp et de petits nombres premiers impairs l_1, ..., l_n. Clés secrètes : Alice choisit a = (a_1, ..., a_n), chaque a_i appartenant à {-m, ..., m} (des petits entiers aléatoires). Bob choisit b = (b_1, ..., b_n). Clé publique d’Alice : E_A = [l_1^a_1 * ... * l_n^a_n] * E0. Clé publique de Bob : E_B = [l_1^b_1 * ... * l_n^b_n] * E0. Secret partagé : Alice applique ses exposants secrets à E_B ; Bob les applique à E_A. La commutativité garantit qu’ils obtiennent tous deux E_AB = [product(l_i^(a_i + b_i))] * E0. Le secret partagé est j(E_AB). Aucun point auxiliaire n’est publié.

L’implémentation de référence de CSIDH utilise p = 4 * l_1 * l_2 * ... * l_74 - 1, où l_1 à l_74 sont les 74 premiers nombres premiers impairs (3, 5, 7, ..., 373). Cela donne un p d’environ 512 bits. Chaque composante a_i de la clé secrète appartient à {-5, ..., 5} (11 choix par composante, 74 composantes). L’ordre du groupe des classes est approximativement égal à sqrt(p), et l’espace des clés contient 11^74 possibilités. Pour calculer chaque étape d’isogénie : pour chaque nombre premier l_i, il faut trouver le sous-groupe de l_i-torsion et calculer l’isogénie de degré l_i à l’aide des formules de Vélu. Avec sqrt-Velu, chaque étape d’isogénie correspondant à un grand nombre premier nécessite O(sqrt(l_i)) opérations. Un échange de clés complet prend environ 1 à 5 ms sur du matériel moderne pour CSIDH-512.

Le CSIDH original n’est pas à temps constant : le nombre d’étapes de Vélu dépend des valeurs de la clé secrète a_i, ce qui provoque une fuite d’informations par des canaux auxiliaires temporels. CTIDH (ISOGENY Diffie-Hellman à temps constant, Bernstein et al., 2021) corrige ce problème en utilisant un format de clé à poids fixe et un calcul d’isogénies à temps constant soigneusement conçu. Les clés secrètes CTIDH sont limitées aux vecteurs dont la somme des valeurs absolues est fixe (par exemple, sum |a_i| = 130). Le calcul des isogénies s’effectue en un nombre fixe d’étapes, quelles que soient les valeurs de la clé secrète, en utilisant des calculs d’isogénies factices pour remplir les étapes où l’exposant secret est nul. CTIDH offre une sécurité comparable à celle de CSIDH-512, avec de strictes garanties de temps constant adaptées aux déploiements sur systèmes embarqués.

La sécurité quantique de CSIDH est plus nuancée que celle des schémas fondés sur les réseaux. La meilleure attaque quantique utilise l’algorithme de Kuperberg (2005) pour le problème du décalage caché, qui compromet la structure de l’action du groupe de classes en temps sous-exponentiel L(1/2) = exp(O(sqrt(log p))). Elle est nettement plus efficace que la meilleure attaque classique en sqrt(p), ce qui signifie que les ordinateurs quantiques affaiblissent considérablement CSIDH par rapport aux attaquants classiques. Pour atteindre une sécurité post-quantique de 128 bits (contre l’attaque L(1/2)), CSIDH nécessite un nombre premier p d’environ 5000 bits (CSIDH-5000), contre 512 bits pour une sécurité classique de 128 bits. On estime que CSIDH-512 n’offre que 62 à 72 bits de sécurité quantique, bien en deçà des exigences du niveau 1 de NIST.

La sécurité de CSIDH repose sur le problème inverse de l’action de groupe (GAIP) : étant donné E_A = a * E0 et E0, trouver a. Le meilleur algorithme connu est une réduction de type Pohlig-Hellman combinée à la méthode des pas de bébé et des pas de géant, avec une complexité classique en O(sqrt(|Cl|)) ~ O(p^{1/4}). La difficulté quantique (Kuperberg) rend CSIDH moins sûr contre les attaques quantiques que les schémas fondés sur LWE. La meilleure attaque quantique contre LWE (le crible de réseaux) offre des marges de sécurité plus prudentes. L’avantage de CSIDH est sa compacité : CSIDH-512 possède des clés publiques de 64 octets (simplement un invariant j), contre 800 octets pour ML-KEM-512. Pour les applications qui exigent les clés les plus petites possible et acceptent des marges de sécurité quantique plus faibles, CSIDH reste intéressant.

Plusieurs variantes de CSIDH cherchent à remédier à ses limites en matière de sécurité quantique. BSIDH (B pour « meilleur ») utilise des courbes de base de degré supérieur et des produits de courbes elliptiques afin d’augmenter la taille du groupe de classes tout en conservant un calcul rapide. Csurf (CSIDH sur la surface) utilise un autre ensemble de courbes supersingulières pour accélérer le calcul de l’action de groupe. Les propositions CSIDH de genre supérieur utilisent les jacobiennes de courbes de genre 2 sur Fp, offrant un espace d’action de groupe plus vaste et potentiellement de meilleures marges de sécurité quantique. Aucune de ces variantes n’a été largement adoptée ni prise en compte par NIST, notamment parce que l’analyse de leur sécurité quantique évolue encore et est moins avancée que celle des schémas fondés sur les réseaux.

CSIDH et SIDH diffèrent sur des points fondamentaux. Commutativité : CSIDH utilise une action de groupe commutative (un groupe de classes) ; SIDH est un échange de clés non interactif fondé sur des isogénies non commutatives et des points de torsion auxiliaires. Corps de base : CSIDH fonctionne sur Fp ; SIDH sur Fp2 (une extension quadratique). Taille de la clé publique : CSIDH fait 64 octets (un seul invariant j sur Fp) ; SIDH fait au moins 324 octets (une courbe et deux points de Fp2). Sécurité : CSIDH a résisté à l’attaque de Castryck-Decru ; SIDH a été compromis. Sécurité quantique : CSIDH nécessite des nombres premiers de 5000 bits pour une sécurité quantique de 128 bits ; SIDH offrait une résistance quantique comparable avant sa compromission classique. Performances : CSIDH-512 s’exécute en environ 1 à 5 ms ; SIDH était similaire, mais CSIDH-5000 serait beaucoup plus lent.

La commutativité de CSIDH permet un échange de clés non interactif (NIKE) : Alice publie E_A = a * E0 ; Bob publie E_B = b * E0. Par la suite, sans aucune communication supplémentaire, n’importe qui peut calculer le secret partagé à partir de l’une ou l’autre des clés publiques : Alice calcule a * E_B = a * (b * E0) = ab * E0 ; Bob calcule b * E_A = b * (a * E0) = ab * E0. Cette propriété NIKE est utile pour les applications dans lesquelles un échange de clés interactif est impraticable — par exemple, le chiffrement des courriels lorsque l’expéditeur et le destinataire ne sont pas connectés simultanément. Le NIKE de CSIDH est analogue au NIKE de Diffie-Hellman, mais post-quantique. ML-KEM (fondé sur LWE) ne prend pas naturellement en charge NIKE sans conception supplémentaire du protocole.

CSIDH n’a pas été normalisé et n’est pas encore déployé dans des systèmes de production. Il fait l’objet de recherches actives et plusieurs implémentations sont disponibles : CTIDH (à temps constant), csidh-reference (Python, à des fins pédagogiques) et supersingular-isogeny-toolbox (C optimisé). Le principal obstacle au déploiement est la sécurité quantique : on estime que les 62 à 72 bits de sécurité quantique de CSIDH-512 sont inférieurs au niveau 1 de NIST (128 bits), ce qui le rend inadapté aux applications post-quantiques exigeant la conformité à NIST. CSIDH-5000 atteindrait le seuil de sécurité, mais serait considérablement plus lent. Les recherches se poursuivent pour améliorer l’analyse de la sécurité quantique et développer des variantes qui comblent cet écart, mais CSIDH reste un prototype de recherche plutôt qu’une primitive prête à être déployée en 2024.

Pourquoi l’action commutative du groupe de classes de CSIDH permet-elle un échange de clés non interactif ?

CSIDH utilise l’action commutative du groupe de classes de Cl(Z[pi]) sur des courbes supersingulières définies sur Fp, où pi est l’endomorphisme de Frobenius. Les clés publiques sont de simples invariants j (64 octets). Aucun point de torsion auxiliaire n’est publié, ce qui évite la vulnérabilité de SIDH. L’action du groupe de classes est commutative, ce qui permet NIKE. La meilleure attaque classique a une complexité en O(p^{1/4}) ; la meilleure attaque quantique (Kuperberg) s’exécute en temps sous-exponentiel L(1/2), ce qui nécessite des nombres premiers de 5000 bits pour une sécurité quantique de 128 bits. CTIDH fournit une implémentation à temps constant. CSIDH-512 n’offre qu’environ 65 bits de sécurité quantique. CSIDH n’est pas normalisé ; les recherches portent sur des variantes qui améliorent la résistance quantique tout en conservant des clés compactes.