Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

Cet article présente une attaque quantique en temps polynomial qui brise les schémas standardisés ML-KEM, Falcon, Hawk et NTRU sur les anneaux cyclotomiques de degré puissance de deux en exploitant une décomposition en tour du problème de l'idéal principal pour atteindre une probabilité de succès élevée avec un facteur d'approximation vérifié.

L'essentiel

La vue d'ensemble : Un crochet quantique pour les coffres-forts numériques

Imaginez que les coffres-forts numériques les plus sécurisés au monde (comme ceux protégeant les secrets gouvernementaux ou les données bancaires) sont construits à l'aide d'un type spécifique de « labyrinthe » mathématique. Ces labyrinthes sont basés sur des formes complexes appelées réseaux. Actuellement, nous pensons que ces labyrinthes sont trop vastes et trop tordus pour que même les superordinateurs les plus rapides puissent les résoudre, c'est pourquoi ils sont considérés comme sûrs pour l'avenir (Cryptographie Post-Quantique).

Ce papier prétend avoir trouvé une clé maître quantique capable de déverrouiller ces labyrinthes spécifiques beaucoup plus rapidement que ce que l'on pensait possible. Les auteurs, dirigés par Ming-Xing Luo, soutiennent qu'un ordinateur quantique n'a pas seulement besoin d'être « rapide » ; il doit être « intelligent » concernant la forme spécifique du labyrinthe. En exploitant un raccourci géométrique caché, ils peuvent briser les schémas de chiffrement que le NIST (l'organisme de normalisation américain) a récemment sélectionnés comme nouvelle norme mondiale.

Le voyage en quatre parties vers la solution

Ce papier est la dernière partie d'une série de quatre. Imaginez cela comme une équipe de quatre détectives résolvant un immense braquage, où chaque détective a résolu une pièce différente de l'énigme :

1. Partie I (La Carte) : Ils ont prouvé que le « terrain » de ces labyrinthes est en réalité très simple. C'est comme découvrir qu'une forêt apparemment complexe est en fait une grille où chaque chemin mène à une seule clairière centrale. Cela signifie qu'il n'y a ni impasses ni boucles cachées qui pourraient confondre l'attaquant.
2. Partie II (La Traduction) : Ils ont montré que l'on peut traduire le problème complexe « Module » (un labyrinthe en 3D) en un problème « Idéal » plus simple (un labyrinthe en 2D) sans perdre beaucoup d'informations. C'est comme réaliser qu'un puzzle en 3D n'est qu'un dessin plat plié ; vous pouvez le déplier facilement.
3. Partie III (La Règle) : Ils ont mesuré le « bruit » dans le système. Dans ces labyrinthes, il y a toujours un peu de statique ou de flou. Ils ont prouvé que ce flou est si petit et prévisible qu'il ne cache pas la solution. C'est comme réaliser que le brouillard dans la forêt est si fin que vous pouvez voir clairement le panneau de sortie.
4. Partie IV (L'Attaque - Ce Papier) : C'est l'exécution. Ils ont combiné la carte, la traduction et la règle en une seule recette étape par étape (un algorithme) qu'un ordinateur quantique peut suivre pour casser le code.

Comment fonctionne l'attaque : L'analogie de la « Tour »

Le cœur de leur attaque est une méthode appelée la Tour Cyclotomique.

Imaginez que vous essayez de grimper à une immense tour de 256 étages pour atteindre le dernier étage où le secret est gardé.

• L'ancienne méthode (Ordinateurs classiques) : Vous essayez de grimper chaque marche une par une. Cela prendrait une éternité (temps exponentiel).
• La méthode quantique (La méthode des auteurs) : Ils ont réalisé que la tour est construite par couches. Au lieu de grimper marche par marche, vous pouvez prendre un ascenseur qui saute d'un étage à l'autre, résolvant un petit puzzle à chaque arrêt.
  • Étape 1 : Allez au 3e étage. Résolvez un petit puzzle.
  • Étape 2 : Allez au 4e étage. Utilisez la réponse du 3e étage pour résoudre un puzzle légèrement plus grand.
  • Étape 3 : Répétez cela jusqu'au sommet.

Parce que la tour est construite selon un motif mathématique spécifique (puissances de 2), cette méthode « d'ascenseur » est incroyablement efficace. Les auteurs prouvent qu'un ordinateur quantique peut effectuer toute cette ascension en temps polynomial. En langage courant : si la tour a 256 étages, un ordinateur classique pourrait prendre plus de temps que l'âge de l'univers, mais un ordinateur quantique pourrait le faire en le temps qu'il faut pour préparer une tasse de café.

Le résultat : Briser les normes

Le papier teste cette méthode contre les normes de chiffrement spécifiques choisies par le NIST :

• ML-KEM (Kyber) : La norme principale pour l'échange de clés sécurisé.
• Falcon & Hawk : Normes pour les signatures numériques (comme une carte d'identité numérique).
• NTRU : Une autre famille de schémas de chiffrement.

Les découvertes :
Les auteurs ont effectué des simulations et des preuves mathématiques montrant que leur algorithme quantique peut casser ces codes avec un taux de réussite de 99 %.

• Ils ont calculé une « marge de sécurité ». Imaginez que la serrure nécessite une clé de 1 665 unités de long pour être brisée. Leur clé quantique n'a que 103 unités de long environ.
• Parce que leur clé est beaucoup plus courte que la longueur requise, la serrure s'ouvre facilement.

Ils affirment que tous les ensembles de paramètres standardisés pour ces schémas sont désormais considérés comme « cassés » si un ordinateur quantique à grande échelle existe.

Le coût : Quelle est la taille de l'ordinateur quantique ?

Vous vous demandez peut-être : « Quelle puissance doit avoir cet ordinateur quantique ? »
Les auteurs ont fait les calculs sur les ressources requises :

• Qubits (Bits quantiques) : Ils estiment qu'il faut environ 1,4 million de qubits physiques (ce qui se traduit par environ 1 400 qubits « logiques » ou corrigés des erreurs).
• Temps : Le calcul prendrait un temps raisonnable, équivalent approximativement au nombre d'opérations qu'un superordinateur moderne effectue en quelques jours, mais exécuté par une machine quantique.

La mise en garde :
Il s'agit d'une percée théorique. Nous n'avons pas actuellement d'ordinateurs quantiques avec 1,4 million de qubits. Cependant, le papier prouve que si nous en construisons un, ces normes de chiffrement spécifiques ne seront pas sûres.

Résumé en une phrase

Ce papier prouve qu'un type spécifique de « labyrinthe » mathématique utilisé dans le chiffrement sécurisé moderne possède un raccourci caché qu'un futur ordinateur quantique peut exploiter, lui permettant de déverrouiller le système avec une clé beaucoup plus petite et plus facile à trouver que ce que l'on croyait auparavant.

Résumé technique

Résumé technique : Attaque quantique probabiliste polynomiale sur Module-LWE sur les cyclotomiques de puissance de 2

Énoncé du problème
L'article traite de la sécurité des schémas cryptographiques basés sur l'apprentissage avec erreurs sur les modules (Module-LWE), en se concentrant spécifiquement sur ML-KEM (anciennement CRYSTALS-Kyber), standardisé par le NIST, et sur des schémas basés sur les réseaux apparentés (Falcon, Hawk, NTRU) construits sur des anneaux cyclotomiques de puissance de 2 ($R = \mathbb{Z}[\zeta_{2^k}]$). Le problème central est la récupération des clés secrètes via le problème du vecteur le plus court (SVP) sur les réseaux de modules. Alors que les attaques classiques reposent sur des algorithmes de réduction de réseau (par exemple BKZ) à complexité exponentielle, l'article examine si un adversaire quantique peut exploiter la structure algébrique des anneaux cyclotomiques pour résoudre efficacement le problème de l'idéal principal (PIP) et le problème du générateur court (SGP).

Les auteurs identifient deux questions critiques non résolues dans les travaux antérieurs (spécifiquement l'attaque CDPR) :

1. Le facteur d'approximation atteint par l'attaque CDPR est-il suffisamment petit pour casser les clés secrètes complètes de ML-KEM (c'est-à-dire, est-ce que $\gamma < q/2$) ?
2. La sous-routine quantique PIP sous-jacente atteint-elle une véritable complexité polynomiale sans surcoûts exponentiels cachés ni dépendance à l'hypothèse de Riemann généralisée (GRH) ?

Méthodologie
L'article présente un pipeline d'attaque unifié en quatre phases (Algorithme 1) qui intègre les résultats des parties I à III de la série avec un nouvel algorithme quantique polynomial pour le PIP (Partie IV).

1. Réduction Module-Ideal : L'attaque commence par réduire l'instance Module-LWE à un problème d'idéal principal. En utilisant une décomposition de Gram-Schmidt, la base du module est transformée en un produit d'idéaux principaux. Les auteurs prouvent que la réduction n'introduit qu'un facteur constant $\alpha_d = O(1)$, indépendant du rang du module $d$.
2. PIP quantique en tour : Au lieu de résoudre le PIP directement dans le corps complet $\mathbb{Q}(\zeta_{2^k})$, les auteurs proposent une stratégie de « décomposition en tour ». Ils décomposent le corps en une chaîne d'extensions quadratiques : $\mathbb{Q} \subset \mathbb{Q}(\zeta_8) \subset \dots \subset \mathbb{Q}(\zeta_{2^k})$.
   • À chaque niveau $L$, l'algorithme résout le PIP pour l'extension relative en utilisant le problème du sous-groupe caché abélien (HSP).
   • Crucialement, le nombre de nouveaux générateurs d'unités à chaque niveau croît linéairement ($\Delta r_L = 2^{L-3}$), maintenant la taille de l'instance HSP polynomiale.
   • Cette approche évite l'explosion des coefficients inhérente aux représentations standards par base de puissance et élimine le besoin de la GRH, car le nombre de classes du sous-corps réel maximal est prouvé être égal à 1 pour $k \le 12$.
3. CVP sur les logarithmes d'unités : Une fois un générateur $g$ de l'idéal trouvé (qui peut être exponentiellement long), l'algorithme calcule son plongement logarithmique. Il résout ensuite le problème du vecteur le plus proche (CVP) sur le réseau des logarithmes d'unités pour trouver l'écart d'unité $\epsilon$ tel que $g = g_0 \epsilon$, où $g_0$ est le générateur court.
   • Les auteurs utilisent l'algorithme du plan le plus proche de Babai. Ils prouvent que pour les générateurs d'anneaux courts, le vecteur cible se trouve dans le « rayon de capture » du réseau, permettant à l'algorithme de Babai de récupérer exactement l'écart d'unité.
4. Récupération du générateur court : L'unité $\epsilon$ est reconstruite à partir de la solution du CVP, et le générateur court est récupéré sous la forme $g_0 = g \cdot \epsilon^{-1}$.

Contributions clés

• PIP quantique polynomial : L'article fournit la première construction d'un algorithme quantique polynomial pour le PIP sur les anneaux cyclotomiques de puissance de 2. La complexité est de $O(n^3 \log^2 n)$ portes quantiques et $O(n^2 \log n)$ qubits, où $n$ est le degré de l'anneau. Cela élimine la surcharge exponentielle précédemment associée à l'algorithme de Biasse-Song.
• Analyse précise du facteur d'approximation : Les auteurs dérivent un facteur d'approximation exact $\gamma = \alpha_d \cdot \exp(\sigma_d \sqrt{2 \ln n})$. Ils prouvent que la variance $\sigma_d$ du plongement logarithmique est $O(1)$ et indépendante du module $q$.
• Vérification du nombre de classes : Le travail repose sur la preuve (de la Partie I) que le nombre de classes du sous-corps réel maximal est trivial ($h^+_k = 1$) pour tout $k \le 12$, garantissant que chaque idéal est principal.
• Extension à plusieurs schémas : Le cadre est étendu au-delà de ML-KEM pour analyser les variantes Falcon, Hawk et NTRU sur les cyclotomiques de puissance de 2, démontrant que les mêmes faiblesses algébriques s'appliquent.

Résultats
Les auteurs fournissent des estimations de sécurité concrètes pour les ensembles de paramètres standardisés :

• ML-KEM-1024 : L'attaque atteint un facteur d'approximation médian $\gamma_{med} \approx 21$ et un facteur au 99e percentile $\gamma_{99\%} \approx 103$. Ces deux valeurs sont nettement inférieures au seuil de sécurité de $q/2 = 1665$. La probabilité de succès est estimée à $\ge 0,99$ pour $d \le 3$ et $\ge 0,90$ pour $d=4$, avec une probabilité d'échec réductible à $< 10^{-6}$ par répétition.
• Estimations des ressources : Pour ML-KEM-1024 ($n=256$), l'attaque nécessite environ $2^{27}$ portes logiques et $1,4 \times 10^6$ qubits physiques (en supposant un code de surface avec une distance de 30).
• Autres schémas :
  • Falcon : L'attaque casse Falcon-512 et Falcon-1024 avec des marges de $72\times$ et $63\times$ respectivement.
  • Hawk : L'attaque casse Hawk-512 et Hawk-1024. Hawk-256 est cassé conditionnellement ; bien que la borne formelle à 99 % dépasse le seuil, les simulations empiriques montrent un taux de succès de 99,99 %.
  • NTRU : L'attaque s'applique aux variantes NTRU-HPS et NTRU-HRSS sur les anneaux cyclotomiques de puissance de 2, atteignant des marges allant de $11\times$ à $45\times$.

Signification et affirmations
L'article prétend résoudre les questions ouvertes concernant l'attaque CDPR en démontrant que :

1. Le facteur d'approximation est suffisamment petit pour casser tous les ensembles de paramètres standardisés de ML-KEM, Falcon, Hawk et NTRU sur les anneaux cyclotomiques de puissance de 2 sous une attaque quantique.
2. Le PIP peut être résolu en temps polynomial véritable ($O(n^3 \log^2 n)$) sans facteurs exponentiels cachés ni dépendance à des conjectures non prouvées en théorie des nombres comme la GRH.
3. La structure algébrique des anneaux cyclotomiques de puissance de 2 permet à un adversaire quantique de réduire le facteur d'approximation de super-polynomial ($\approx 2^{54}$ dans les estimations précédentes) à sous-polynomial ($\approx 2^{21}$), cassant efficacement les hypothèses de sécurité de ces candidats post-quantiques.

Les auteurs notent que bien que l'attaque soit probabiliste, la probabilité d'échec est faible et peut être atténuée par des répétitions indépendantes. Ils soulignent que les résultats reposent sur les propriétés algébriques spécifiques des anneaux cyclotomiques de puissance de 2 et sur la trivialité du nombre de classes pour $k \le 12$.