L’avenir de la cryptographie fondée sur les isogénies

La compromission de SIKE par Castryck-Decru en juillet 2022 a profondément transformé le domaine. Avant cette compromission, la cryptographie fondée sur les isogénies était une voie post-quantique prometteuse, caractérisée par de petites tailles de clés, des efforts actifs de normalisation et une communauté en plein essor. Après la chute de SIKE, le domaine a dû réexaminer ses fondements. La question centrale est la suivante : quels aspects de la cryptographie fondée sur les isogénies restent-ils difficiles après l’apparition des nouvelles techniques d’isogénies de Richelot ? La réponse semble être la suivante : la difficulté fondée sur les anneaux d’endomorphismes (utilisée dans SQISign) et les actions commutatives de groupes de classes (CSIDH) restent intactes. La fuite de points de torsion auxiliaires propre à SIDH est l’élément compromis, et non les isogénies en général.

SQISign (signature courte fondée sur les quaternions et les isogénies, De Feo et al., 2020) est le schéma de signature post-quantique connu le plus compact. Clé publique : 64 octets (un invariant j supersingulier). Signature : 177 octets au niveau 1. À titre de comparaison, ML-DSA (Dilithium) possède des clés publiques de 1312 octets et des signatures de 2420 octets au niveau 2. La sécurité de SQISign repose sur la correspondance de Deuring : le problème consistant à calculer une isogénie de degré prescrit entre deux courbes supersingulières données équivaut à trouver un idéal dans l’algèbre quaternionique de l’anneau des endomorphismes. SQISign utilise un schéma d’identification de Fiat-Shamir fondé sur ce problème difficile et produit une signature sous la forme d’une représentation compressée de l’isogénie de réponse.

La compacité de SQISign se paie par un coût très élevé en matière de performances. La signature nécessite le calcul d’une isogénie de grand degré (environ p^{1/4}) au moyen de la conversion d’un idéal en isogénie dans l’algèbre quaternionique — une opération exigeante en calcul, qui prend environ 60 à 600 secondes sur un CPU de bureau, selon le jeu de paramètres. La vérification est plus rapide (environ 200 ms), mais reste bien plus lente que la vérification de ML-DSA (quelques microsecondes). SQISign 2.0 (2023) a amélioré les performances d’un facteur 100 grâce à des améliorations algorithmiques, ramenant la durée de signature à 1 à 10 secondes. SQISign HD (haut degré) et d’autres variantes poursuivent l’optimisation. L’application visée concerne les cas d’usage où la bande passante est fortement limitée (certificats IoT, données de chaîne de blocs, communications spatiales) et où la vitesse de calcul est secondaire.

FESTA (chiffrement rapide fondé sur des attaques de torsion supersingulière, 2023) est un KEM conçu explicitement pour éviter les fuites de points de torsion de type SIDH. L’idée centrale de la conception est la suivante : au lieu de publier phi_A(P_B) et phi_A(Q_B) comme dans SIDH, FESTA utilise une structure d’isogénie différente dans laquelle la clé publique du chiffreur est uniquement la courbe image (sans images de torsion). FESTA utilise les isogénies 2^n d’une manière modifiée qui permet le déchiffrement sans publier les images de la base de torsion de l’autre partie. Les premières analyses indiquent que FESTA résiste à l’attaque de Castryck-Decru grâce à la structure différente de ses informations auxiliaires. FESTA est une voie prometteuse, mais nécessite un examen cryptanalytique plus approfondi — la communauté des isogénies reste prudente après la compromission surprise de SIKE.

SCALLOP (actions commutatives extensibles avec de grands nombres premiers orientés, 2023) s’attaque à la faiblesse de CSIDH en matière de sécurité quantique. Le petit nombre premier p de 512 bits de CSIDH n’offre qu’environ 65 bits de sécurité quantique (en raison de l’algorithme sous-exponentiel de Kuperberg). SCALLOP utilise une structure algébrique différente : des courbes à multiplication complexe par de grands ordres quadratiques imaginaires, dont le groupe de classes est spécialement conçu pour résister aux attaques quantiques de type Kuperberg. SCALLOP obtient un groupe de classes effectif plus grand, avec des paramètres offrant une sécurité quantique de 128 bits pour des tailles de paramètres inférieures à celles de CSIDH-5000. Le compromis est le suivant : la configuration algébrique de SCALLOP est plus complexe et a fait l’objet de moins d’analyses indépendantes que CSIDH.

Compte tenu de la compacité particulière des schémas fondés sur les isogénies (signatures de 177 octets pour SQISign, clés de 64 octets pour CSIDH) et de leurs hypothèses de difficulté distinctes de celles des schémas fondés sur les réseaux, des constructions hybrides combinent des composants fondés sur les isogénies et sur les réseaux pour fournir une défense en profondeur. Dans un KEM hybride, on encapsule avec ML-KEM-512 ET avec CSIDH-512, puis on hache les deux secrets ensemble. La clé combinée nécessite de casser simultanément ML-KEM (difficulté de LWE) et CSIDH (action du groupe de classes). Si l’un des deux reste intact, l’hybride est sûr. Cette approche d’agilité cryptographique est soutenue par NIST et NSA pour les organisations qui souhaitent une assurance supplémentaire au-delà de toute primitive post-quantique unique, notamment lorsque le calendrier d’apparition des ordinateurs quantiques reste incertain.

Les preuves à divulgation nulle de connaissance fondées sur les isogénies constituent une voie de recherche émergente. Le problème du chemin d’isogénie (trouver phi: E -> E' étant données les deux courbes) peut servir de problème difficile pour les schémas de preuve de connaissance. Les protocoles Sigma pour « Je connais une isogénie de E vers E' » permettent l’authentification sans révéler l’isogénie. Vero (2022) présente un système pratique de preuve ZK fondé sur les isogénies. Ces preuves ZK sont naturellement compactes (l’énoncé se résume à deux invariants j), mais elles sont actuellement trop lentes pour un déploiement pratique. À mesure que le calcul des isogénies progresse, les preuves ZK fondées sur les isogénies pourraient constituer une solution de remplacement aux preuves fondées sur les réseaux ou sur les fonctions de hachage, lorsque la diversité des hypothèses est privilégiée.

Les techniques d’isogénie ne sont pas seulement pertinentes pour la cryptographie post-quantique : elles ont aussi des applications en cryptographie classique à courbes elliptiques. L’algorithme de Schoof-Elkies-Atkin (SEA) de dénombrement des points sur les courbes elliptiques utilise les isogénies pour calculer la trace de Frobenius, ce qui permet de générer efficacement des paramètres sûrs de courbes elliptiques. Les isogénies apparaissent dans les améliorations de la méthode rho de Pollard pour le calcul de ECDLP. La méthode CM (multiplication complexe) de construction de courbes d’ordre prescrit utilise des polynômes de classes qui sont fondamentalement des objets liés aux isogénies. Les outils de cryptanalyse fondés sur les isogénies (recherche de chemins d’isogénies de degré lisse) servent à évaluer les paramètres proposés pour les courbes elliptiques afin d’y détecter d’éventuelles portes dérobées cachées — ce qui est directement lié aux préoccupations concernant Dual EC DRBG.

En 2024, aucun schéma fondé sur les isogénies n’est normalisé par NIST ni par d’autres organismes majeurs. Le processus PQC de NIST a normalisé ML-KEM, ML-DSA, SLH-DSA et FN-DSA — tous fondés sur les réseaux ou sur les fonctions de hachage. NIST mène un deuxième tour d’évaluation des signatures PQC ; SQISign a été soumis, mais suscite des inquiétudes concernant ses performances. La communauté des isogénies travaille à une version SQISign 3.0 plus aboutie, avec des temps de signature pratiques (objectif inférieur à la seconde). ISO et ETSI n’ont normalisé aucun schéma fondé sur les isogénies. La voie de normalisation à court terme la plus probable est SQISign pour des applications de niche exigeant des signatures de taille minimale, éventuellement sous la forme d’une norme informative plutôt que d’une primitive obligatoire. Un déploiement à grande échelle nécessiterait des améliorations des performances d’un ordre de grandeur.

Axes de recherche actifs en cryptographie fondée sur les isogénies en 2024 : (1) variantes de SQISign (SQISign 2.0, HD, SQISign rapide) améliorant les performances de signature pour parvenir à une exécution en moins d’une seconde. (2) Analyse de la sécurité quantique de CSIDH et de ses variantes — affinement des estimations liées à l’attaque de Kuperberg et exploration de structures algébriques qui lui résistent. (3) Nouvelles hypothèses de difficulté — calculs d’anneaux d’endomorphismes supersinguliers et problèmes de modules sur des anneaux quadratiques imaginaires. (4) Fonctions pseudo-aléatoires oblivieuses fondées sur les isogénies et applications aux protocoles préservant la confidentialité. (5) Implémentations matérielles de l’arithmétique des isogénies — exploitation du parallélisme des FPGA pour l’action du groupe de classes de CSIDH. (6) Intégration des actions de groupe fondées sur les isogénies dans des cadres génériques de cryptographie des actions de groupe pour créer de nouveaux schémas de chiffrement fonctionnel et fondés sur les attributs.

La rupture de SIKE pourrait laisser penser qu'il faut abandonner entièrement la cryptographie fondée sur les isogénies. La communauté cryptographique adopte le point de vue opposé : cette rupture a été précieuse précisément parce qu'elle a permis d'identifier les structures qui ne sont pas sûres (la fuite des points de torsion de SIDH) et celles qui restent difficiles à résoudre (les anneaux d'endomorphismes et les actions de groupes de classes). Étudier les isogénies reste important pour : (1) la diversité post-quantique — disposer d'hypothèses de sécurité autres que les réseaux réduit le risque systémique si LWE est compromis ; (2) SQISign fournit des signatures exceptionnellement compactes, sans équivalent actuel ; (3) les techniques fondées sur les isogénies contribuent à la cryptanalyse des courbes elliptiques et à la validation des paramètres ; (4) les mathématiques sont belles et fécondes — les outils développés pour la rupture de SIKE ont directement amélioré la compréhension des anneaux d'endomorphismes des courbes elliptiques, utilisés dans d'autres contextes.

Quelle hypothèse de difficulté sous-tend les signatures SQISign ?

Après la rupture de SIKE en 2022, la cryptographie fondée sur les isogénies se poursuit avec d'autres hypothèses de difficulté. SQISign fournit des signatures post-quantiques de 177 octets (les plus petites connues), fondées sur la difficulté des anneaux d'endomorphismes ; ses performances s'améliorent, avec pour objectif de passer sous la seconde. Les constructions FESTA contournent la fuite des points de torsion de SIDH pour les mécanismes d'encapsulation de clés. SCALLOP vise une sécurité quantique de 128 bits grâce à des courbes orientées. Les schémas hybrides combinant isogénies et réseaux diversifient les hypothèses de sécurité. Aucun schéma fondé sur les isogénies n'est actuellement normalisé. La normalisation de SQISign est la voie la plus probable à court terme. La rupture de SIKE a permis de mieux comprendre ce qui doit rester caché dans les protocoles fondés sur les isogénies et a produit de nouveaux outils mathématiques utilisés dans toute la cryptographie des courbes elliptiques.