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

Dieser Artikel stellt einen quantenmechanischen Angriff in polynomieller Laufzeit vor, der standardisierte ML-KEM-, Falcon-, Hawk- und NTRU-Schemata über 2-Potenz-zyklotomischen Ringen durchbricht, indem er eine Turmzerlegung des Hauptidealproblems nutzt, um mit einem verifizierten Approximationsfaktor eine hohe Erfolgswahrscheinlichkeit zu erreichen.

Das Wesentliche

Das große Ganze: Ein quantenmechanischer Dietrich für digitale Tresore

Stellen Sie sich vor, die sichersten digitalen Tresore der Welt (wie diejenigen, die Regierungsgeheimnisse oder Bankdaten schützen), sind mit einer bestimmten Art mathematischem „Labyrinth" gebaut. Diese Labyrinthe basieren auf komplexen Formen, die Gitter genannt werden. Derzeit gehen wir davon aus, dass diese Labyrinthe zu groß und verschlungen sind, um sie selbst mit den schnellsten Supercomputern zu lösen, weshalb sie als sicher für die Zukunft gelten (Post-Quanten-Kryptografie).

Dieses Papier behauptet, einen quantenmechanischen Meister-Schlüssel gefunden zu haben, der diese spezifischen Labyrinthe viel schneller öffnen kann, als bisher für möglich gehalten wurde. Die Autoren, angeführt von Ming-Xing Luo, argumentieren, dass ein Quantencomputer nicht nur „schnell" sein muss; er muss bezüglich der spezifischen Form des Labyrinths „schlau" sein. Indem sie einen versteckten geometrischen Abkürzungsweg ausnutzen, können sie die Verschlüsselungsschemata brechen, die NIST (das US-amerikanische Normungsgremium) kürzlich als neuen globalen Standard ausgewählt hat.

Die vierstufige Reise zur Lösung

Das Papier ist der letzte Teil einer vierteiligen Serie. Stellen Sie es sich wie ein Team aus vier Detektiven vor, die einen massiven Raubüberfall aufklären, wobei jeder Detektiv ein anderes Puzzleteil gelöst hat:

1. Teil I (Die Karte): Sie bewiesen, dass das „Gelände" dieser Labyrinthe tatsächlich sehr einfach ist. Es ist, als würde man entdecken, dass ein scheinbar komplexer Wald tatsächlich ein Gitter ist, bei dem jeder Pfad zu einer einzigen, zentralen Lichtung führt. Das bedeutet, es gibt keine Sackgassen oder versteckte Schleifen, die den Angreifer verwirren würden.
2. Teil II (Die Übersetzung): Sie zeigten, dass man das komplexe „Modul"-Problem (ein 3D-Labyrinth) in ein einfacheres „Ideal"-Problem (ein 2D-Labyrinth) übersetzen kann, ohne viel Information zu verlieren. Es ist, als würde man erkennen, dass ein 3D-Puzzle nur eine flache Zeichnung ist, die zusammengefaltet wurde; man kann sie leicht entfalten.
3. Teil III (Das Lineal): Sie maßen das „Rauschen" im System. In diesen Labyrinthen gibt es immer ein wenig statisches Rauschen oder Unschärfe. Sie bewiesen, dass diese Unschärfe so klein und vorhersehbar ist, dass sie die Lösung nicht verbirgt. Es ist, als würde man erkennen, dass der Nebel im Wald so dünn ist, dass man das Ausgangsschild klar sehen kann.
4. Teil IV (Der Angriff – Dieses Papier): Dies ist die Ausführung. Sie kombinierten die Karte, die Übersetzung und das Lineal zu einem einzigen, schrittweisen Rezept (einem Algorithmus), dem ein Quantencomputer folgen kann, um den Code zu brechen.

Wie der Angriff funktioniert: Die „Turm"-Analogie

Der Kern ihres Angriffs ist eine Methode namens Zyklotomischer Turm.

Stellen Sie sich vor, Sie versuchen, einen massiven, 256-stöckigen Turm zu erklimmen, um die oberste Etage zu erreichen, in der das Geheimnis aufbewahrt wird.

• Der alte Weg (Klassische Computer): Sie versuchen, jede einzelne Stufe nacheinander zu erklimmen. Das würde ewig dauern (exponentielle Zeit).
• Der quantenmechanische Weg (Die Methode der Autoren): Sie erkannten, dass der Turm in Schichten gebaut ist. Anstatt Schritt für Schritt zu klettern, können Sie einen Aufzug nehmen, der von einer Etage zur nächsten springt und an jeder Haltestelle ein winziges Puzzle löst.
  • Schritt 1: Gehen Sie in die 3. Etage. Lösen Sie ein winziges Puzzle.
  • Schritt 2: Gehen Sie in die 4. Etage. Nutzen Sie die Antwort aus der 3. Etage, um ein etwas größeres Puzzle zu lösen.
  • Schritt 3: Wiederholen Sie dies bis ganz nach oben.

Da der Turm in einem spezifischen mathematischen Muster (Potenzen von 2) gebaut ist, ist diese „Aufzug"-Methode unglaublich effizient. Die Autoren beweisen, dass ein Quantencomputer diesen gesamten Aufstieg in polynomieller Zeit bewältigen kann. Auf Deutsch gesagt: Wenn der Turm 256 Stockwerke hat, könnte ein klassischer Computer länger brauchen als das Alter des Universums, aber ein Quantencomputer könnte es in der Zeit schaffen, die zum Aufbrühen einer Tasse Kaffee benötigt wird.

Das Ergebnis: Brechen der Standards

Das Papier testet diese Methode gegen die spezifischen Verschlüsselungsstandards, die NIST ausgewählt hat:

• ML-KEM (Kyber): Der primäre Standard für den sicheren Schlüsselaustausch.
• Falcon & Hawk: Standards für digitale Signaturen (wie eine digitale Ausweis-Karte).
• NTRU: Eine weitere Familie von Verschlüsselungsschemata.

Die Erkenntnisse:
Die Autoren führten Simulationen und mathematische Beweise durch, die zeigen, dass ihr quantenmechanischer Algorithmus diese Codes mit einer Erfolgsrate von 99 % brechen kann.

• Sie berechneten einen „Sicherheitsrand". Stellen Sie sich vor, das Schloss erfordert einen Schlüssel, der 1.665 Einheiten lang ist, um gebrochen zu werden. Ihr quantenmechanischer Schlüssel ist nur etwa 103 Einheiten lang.
• Da ihr Schlüssel so viel kürzer ist als die erforderliche Länge, fällt das Schloss leicht auf.

Sie behaupten, dass alle standardisierten Parametersätze für diese Schemata nun als „gebrochen" gelten, wenn ein großskaliger Quantencomputer existiert.

Der Preis: Wie groß ist der Quantencomputer?

Sie fragen sich vielleicht: „Wie leistungsfähig muss dieser Quantencomputer sein?"
Die Autoren haben die Mathematik für die erforderlichen Ressourcen durchgerechnet:

• Qubits (Quantenbits): Sie schätzen, dass Sie etwa 1,4 Millionen physikalische Qubits benötigen (was ungefähr 1.400 „logischen" oder fehlerkorrigierten Qubits entspricht).
• Zeit: Die Berechnung würde eine angemessene Zeitspanne dauern, grob äquivalent zur Anzahl der Operationen, die ein moderner Supercomputer in wenigen Tagen durchführt, aber ausgeführt von einer Quantenmaschine.

Der Haken:
Dies ist ein theoretischer Durchbruch. Wir haben derzeit keine Quantencomputer mit 1,4 Millionen Qubits. Das Papier beweist jedoch, dass wenn wir einen bauen, diese spezifischen Verschlüsselungsstandards nicht sicher sein werden.

Zusammenfassung in einem Satz

Dieses Papier beweist, dass eine bestimmte Art mathematischem „Labyrinth", das in der modernen sicheren Verschlüsselung verwendet wird, einen versteckten Abkürzungsweg hat, den ein zukünftiger Quantencomputer ausnutzen kann, wodurch er das System mit einem Schlüssel entsperren kann, der viel kleiner und leichter zu finden ist als bisher angenommen.

Technische Zusammenfassung

Technische Zusammenfassung: Probabilistischer polynomieller Quantenangriff auf Module-LWE über 2-Potenz-Zyklotomik

Problemstellung
Der Artikel behandelt die Sicherheit von auf Module Learning With Errors (Module-LWE) basierenden kryptografischen Schemata, mit besonderem Fokus auf die vom NIST standardisierte ML-KEM (ehemals CRYSTALS-Kyber) und verwandte, auf Gittern basierende Schemata (Falcon, Hawk, NTRU), die über 2-Potenz-Zyklotomik-Ringe ($R = \mathbb{Z}[\zeta_{2^k}]$) konstruiert sind. Das zentrale Problem ist die Wiederherstellung von geheimen Schlüsseln mittels des Problems des kürzesten Vektors (SVP) auf Modul-Gittern. Während klassische Angriffe auf Gitterreduktionsalgorithmen (z. B. BKZ) mit exponentieller Komplexität zurückgreifen, untersucht der Artikel, ob ein quantenmechanischer Angreifer die algebraische Struktur zyklotomischer Ringe ausnutzen kann, um das Problem des Hauptideals (PIP) und das Problem des kurzen Generators (SGP) effizient zu lösen.

Die Autoren identifizieren zwei kritische, in früheren Arbeiten (insbesondere dem CDPR-Angriff) ungelöste Fragen:

1. Ist der Approximationsfaktor, der durch den CDPR-Angriff erreicht wird, hinreichend klein, um vollständige ML-KEM-geheime Schlüssel zu brechen (d. h. ist $\gamma < q/2$)?
2. Erreicht die zugrundeliegende quantenmechanische PIP-Subroutine eine wahre polynomielle Zeitkomplexität ohne versteckte exponentielle Overheads oder eine Abhängigkeit von der verallgemeinerten Riemannschen Vermutung (GRH)?

Methodik
Der Artikel stellt eine einheitliche, vierphasige Angriffs-Pipeline (Algorithmus 1) vor, die Ergebnisse aus Teilen I–III der Serie mit einem neuen polynomiellen Quantenalgorithmus für PIP (Teil IV) integriert.

1. Reduktion von Modul zu Ideal: Der Angriff beginnt mit der Reduktion der Module-LWE-Instanz auf ein Problem des Hauptideals. Mithilfe einer Gram-Schmidt-Zerlegung wird die Modulbasis in ein Produkt von Hauptidealen transformiert. Die Autoren beweisen, dass die Reduktion nur einen konstanten Faktor $\alpha_d = O(1)$ einführt, der unabhängig vom Modulrang $d$ ist.
2. Quanten-Turm-PIP: Anstatt das PIP im vollen Körper $\mathbb{Q}(\zeta_{2^k})$ direkt zu lösen, schlagen die Autoren eine Strategie der „Turmzerlegung" vor. Sie zerlegen den Körper in eine Kette quadratischer Erweiterungen: $\mathbb{Q} \subset \mathbb{Q}(\zeta_8) \subset \dots \subset \mathbb{Q}(\zeta_{2^k})$.
   • Auf jeder Ebene $L$ löst der Algorithmus das PIP für die relative Erweiterung unter Verwendung des abelschen versteckten Untergruppenproblems (HSP).
   • Entscheidend ist, dass die Anzahl der neuen Einheitsgeneratoren auf jeder Ebene linear wächst ($\Delta r_L = 2^{L-3}$), wodurch die HSP-Instanzgröße polynomiell bleibt.
   • Dieser Ansatz vermeidet die in Standarddarstellungen mit Potenzbasen inhärente Koeffizientenexplosion und eliminiert die Notwendigkeit der GRH, da die Klassenzahl des maximalen reellen Teilkörpers für $k \le 12$ als 1 bewiesen ist.
3. Log-Einheit-CVP: Sobald ein Generator $g$ des Ideals gefunden wurde (der exponentiell lang sein kann), berechnet der Algorithmus seine Log-Einbettung. Anschließend wird das Problem des nächsten Vektors (CVP) auf dem Log-Einheitsgitter gelöst, um die Einheitsabweichung $\epsilon$ zu finden, sodass $g = g_0 \epsilon$ gilt, wobei $g_0$ der kurze Generator ist.
   • Die Autoren nutzen den Babai-Nächste-Ebene-Algorithmus. Sie beweisen, dass für kurze Ringgeneratoren der Zielvektor innerhalb des „Einfangradius" des Gitters liegt, was es dem Babai-Algorithmus ermöglicht, die Einheitsabweichung exakt wiederherzustellen.
4. Wiederherstellung des kurzen Generators: Die Einheit $\epsilon$ wird aus der CVP-Lösung rekonstruiert, und der kurze Generator wird als $g_0 = g \cdot \epsilon^{-1}$ wiederhergestellt.

Hauptbeiträge

• Polynomieller Quanten-PIP: Der Artikel liefert die erste Konstruktion eines polynomiellen Quantenalgorithmus für das PIP über 2-Potenz-Zyklotomik-Ringe. Die Komplexität beträgt $O(n^3 \log^2 n)$ Quantengatter und $O(n^2 \log n)$ Qubits, wobei $n$ der Grad des Rings ist. Dies entfernt den exponentiellen Overhead, der zuvor mit dem Biasse-Song-Algorithmus verbunden war.
• Präzise Analyse des Approximationsfaktors: Die Autoren leiten einen exakten Approximationsfaktor $\gamma = \alpha_d \cdot \exp(\sigma_d \sqrt{2 \ln n})$ ab. Sie beweisen, dass die Varianz $\sigma_d$ der Log-Einbettung $O(1)$ ist und unabhängig vom Modul $q$ ist.
• Verifizierung der Klassenzahl: Die Arbeit stützt sich auf den Beweis (aus Teil I), dass die Klassenzahl des maximalen reellen Teilkörpers für alle $k \le 12$ trivial ist ($h^+_k = 1$), was sicherstellt, dass jedes Ideal ein Hauptideal ist.
• Erweiterung auf mehrere Schemata: Das Framework wird über ML-KEM hinaus erweitert, um Falcon, Hawk und NTRU-Varianten über 2-Potenz-Zyklotomik zu analysieren, und zeigt, dass dieselben algebraischen Schwachstellen gelten.

Ergebnisse
Die Autoren liefern konkrete Sicherheitsabschätzungen für standardisierte Parametersätze:

• ML-KEM-1024: Der Angriff erreicht einen medianen Approximationsfaktor $\gamma_{med} \approx 21$ und einen 99. Perzentil-Faktor $\gamma_{99\%} \approx 103$. Beide Werte liegen deutlich unter der Sicherheitsschwelle von $q/2 = 1665$. Die Erfolgswahrscheinlichkeit wird für $d \le 3$ auf $\ge 0,99$ und für $d=4$ auf $\ge 0,90$ geschätzt, wobei die Ausfallwahrscheinlichkeit durch Wiederholung auf $< 10^{-6}$ reduziert werden kann.
• Ressourcenabschätzungen: Für ML-KEM-1024 ($n=256$) erfordert der Angriff ungefähr $2^{27}$ logische Gatter und $1,4 \times 10^6$ physikalische Qubits (unter der Annahme eines Surface-Code mit Abstand 30).
• Andere Schemata:
  • Falcon: Der Angriff bricht Falcon-512 und Falcon-1024 mit Margen von $72\times$ bzw. $63\times$.
  • Hawk: Der Angriff bricht Hawk-512 und Hawk-1024. Hawk-256 ist bedingt gebrochen; während die formale 99%-Schranke die Schwelle überschreitet, zeigen empirische Simulationen eine Erfolgsrate von 99,99 %.
  • NTRU: Der Angriff gilt für NTRU-HPS- und NTRU-HRSS-Varianten über 2-Potenz-Zyklotomik-Ringe und erreicht Margen im Bereich von $11\times$ bis $45\times$.

Bedeutung und Behauptungen
Der Artikel behauptet, die offenen Fragen bezüglich des CDPR-Angriffs zu klären, indem er zeigt, dass:

1. Der Approximationsfaktor klein genug ist, um alle standardisierten ML-KEM-, Falcon-, Hawk- und NTRU-Parametersätze über 2-Potenz-Zyklotomik-Ringe unter einem Quantenangriff zu brechen.
2. Das PIP in wahrer polynomieller Zeit ($O(n^3 \log^2 n)$) gelöst werden kann, ohne versteckte exponentielle Faktoren oder eine Abhängigkeit von unbewiesenen zahlentheoretischen Vermutungen wie der GRH.
3. Die algebraische Struktur von 2-Potenz-Zyklotomik-Ringen es einem quantenmechanischen Angreifer ermöglicht, den Approximationsfaktor von superpolynomiell ($\approx 2^{54}$ in früheren Abschätzungen) auf subpolynomiell ($\approx 2^{21}$) zu reduzieren, was die Sicherheitsannahmen dieser postquanten-kryptografischen Kandidaten effektiv bricht.

Die Autoren weisen darauf hin, dass der Angriff zwar probabilistisch ist, die Ausfallwahrscheinlichkeit jedoch gering ist und durch unabhängige Wiederholungen gemindert werden kann. Sie betonen, dass die Ergebnisse auf den spezifischen algebraischen Eigenschaften von 2-Potenz-Zyklotomik-Ringen und der Trivialität der Klassenzahl für $k \le 12$ beruhen.