Was die Dihedral-Coset-Behauptung für die Gitterstandards bedeutet

Ein auf den 31. Juli datiertes Papier, das diese Woche im Cryptology ePrint Archive erschienen ist, behauptet einen quantenpolynomiellen Algorithmus für das Dihedral Coset Problem. Der Autor ist Daniel R. Simon von der AWS Cryptography Group, bekannt für die Orakeltrennung von 1994, die Shors Algorithmus angeregt hat. Zusammen mit Reduktionen, die Regev 2004 veröffentlicht und Brakerski, Kirshanova, Stehlé und Wen 2018 verbessert haben, würde der behauptete Algorithmus das approximative SVP innerhalb eines Faktors von √n polylog(n) lösen und LWE bei vergleichbaren Rauschraten, in quantenpolynomieller Zeit. Diese Parameter reichen an die Annahmen hinter den ausgerollten Gitterstandards heran. Das Papier greift keinen konkreten Parametersatz an.

Was das Papier behauptet

Regev hat 2004 gezeigt, dass ein Dihedral-Löser Gitterprobleme bricht, und er gab einen quantenpolynomiellen Algorithmus für das Dihedral-Problem an, der jedoch ein Subset-Sum-Orakel benötigte, das niemand hat. Kuperbergs Algorithmus kommt ohne Orakel aus, verlangt aber fehlerfreie Samples und läuft in Zeit 2^O(√n). Die Gitterreduktionen liefern fehlerhafte Samples, sodass die Kombination die klassische Gitterreduktion nie geschlagen hat. Der Entwurf ersetzt den Orakelschritt durch ein Hadamard-und-Messen-Verfahren über Gruppen von Samples und behauptet Toleranz gegenüber einer Fehlerrate der Samples von bis zu 1/O(log n), genug, um die Samples anzunehmen, die die Reduktionen bei nützlichen Approximationsfaktoren liefern. Zwanzig Jahre Arbeit am Dihedral-Weg sind an genau diesem Schritt hängen geblieben.

Was das Papier nicht belegt

Der Titel sagt vorläufiger Entwurf. Die tragenden Lemmata sind Beweisskizzen. Zwei Zitate sind persönliche Mitteilungen, und diese beiden stützen das zentrale Korollar. Die Konstruktion ist asymptotisch und zieht kn^c+1 Quanten-Samples mit c von mindestens 12, sodass selbst ein korrekter Beweis keinen Angriff auf irgendeinen konkreten Parametersatz beziffert. Die klassische Sicherheit bleibt unberührt. Nichts in dem Papier betrifft Daten, die heute gegen klassische Angreifer geschützt sind.

Der Präzedenzfall ist Yilei Chens Behauptung vom April 2024, einen quantenpolynomiellen Algorithmus für LWE gefunden zu haben. Hongxun Wu und Thomas Vidick fanden acht Tage nach der Veröffentlichung unabhängig voneinander einen Fehler, den der Autor nicht beheben konnte, und die Behauptung wurde zurückgezogen. Vidick steht in der Danksagung des neuen Entwurfs, die Gutachter, die einen fatalen Fehler am ehesten finden, haben ihn also gesehen. Drei Entwicklungen würden den Stand klären: ein fachliches Urteil der Gitter-Community über den Beweis, eine Überarbeitung, die die Skizzen durch vollständige Argumente ersetzt, oder ein benanntes Gegenbeispiel zu den Amplitudenaussagen in den Lemmata 3 und 4. Keine davon ist eingetreten. Aus dem Papier folgt heute keine Schlussfolgerung über die Sicherheit von ML-KEM.

Erste Reaktionen

Die ersten Reaktionen kamen innerhalb eines Tages und teilten sich entlang vertrauter Linien. Daniel Bernstein schrieb, dass seine Empfehlungen gelten, ob der Beweis Bestand hat oder nicht: „use the largest parameters you can afford; keep the ECC seatbelt; keep investing in alternatives.“ Chris Peikert entgegnete, dass ein Angriff, der in sich zusammenfällt, den Status quo unverändert lässt, ein weiterer ernsthafter Versuch eines Quantenexperten, der gescheitert ist. Die Meinungsverschiedenheit dreht sich darum, wie viel Vertrauen Gitterannahmen verdienen. Keine der beiden Positionen ändert die operative Arbeit, und Bernsteins drei Empfehlungen lösen sich in Eigenschaften auf, die ein Scanner aus einem Bestand ausliest: verwendete Parametergrößen, Hybridpräsenz pro Verbindung und die Verteilung der Algorithmenfamilien über die Assets.

Reichweite, falls der Beweis hält

Die betroffene Familie ist die Gitterkryptographie: ML-KEM (FIPS 203), ML-DSA (FIPS 204), reine LWE-Verfahren wie FrodoKEM und gitterbasierte homomorphe Verschlüsselung. Die Kette von einem Dihedral-Löser zu diesen Standards läuft über veröffentlichte Reduktionen. Brakerski, Kirshanova, Stehlé und Wen haben 2018 die Äquivalenz von LWE und extrapolierten dihedralen Nebenklassen bewiesen. Wen und Zheng setzen Module-LWE, die Annahme unter ML-KEM und ML-DSA, in ePrint 2026/155 zu einer strukturierten Variante in Beziehung, die sie stEDCP nennen. Ihr Abstract nennt eine Richtung dieser Beziehung. Die Richtung, die ein Angreifer braucht, von einem Dihedral-Löser zu einem Module-LWE-Löser, steht im vollständigen Papier und verdient eine Bestätigung, bevor ML-KEM als erfasst gilt. FN-DSA beruht auf NTRU-Gittern und liegt außerhalb der LWE-Kette, wobei ein allgemeiner Algorithmus für approximatives SVP mit polynomiellem Faktor eigene Fragen für NTRU-Schlüssel aufwerfen würde. Außerhalb der Familie stehen SLH-DSA (FIPS 205, hashbasiert), die codebasierten KEMs Classic McEliece und HQC sowie die symmetrische Kryptographie bei ausreichenden Schlüssellängen.

Für alle, deren Bedrohungsmodell aufgezeichneten Verkehr einschließt, folgen zwei Konsequenzen. Vertraulichkeit, die allein auf gitterbasiertem Schlüsselaustausch beruht, tritt neben RSA und ECDH in die Harvest-now-decrypt-later-Klasse ein, lesbar sobald eine hinreichend leistungsfähige Maschine existiert. Hybrider Schlüsselaustausch wie X25519 mit ML-KEM schützt gegen einen klassischen Bruch von ML-KEM, und er schützt nicht gegen dieses Szenario, in dem ein kryptographisch relevanter Quantenrechner beide Komponenten überwindet, Shor auf der Kurve und den Dihedral-Weg auf dem Gitter. Die Absicherung gegen ein Versagen der Familie ist Vielfalt über mathematische Annahmen hinweg. Der technische Aufwand der wichtigsten codebasierten Alternative ist heute messbar, und [PQ]math enthält für diesen Vergleich eine Voreinstellung für Classic McEliece.

Was das für die Migrationsplanung bedeutet

Der operative Test kam vor jedem Urteil über die Korrektheit. Innerhalb von Stunden nach einem solchen Papier sollte ein Sicherheitsteam eine Abfrage beantworten können: welche Assets eine Gitterannahme als einzigen Post-Quanten-Mechanismus haben. Das ist ein Filter über eine kryptographische Stückliste nach Algorithmenfamilie. Ein CycloneDX-1.6-CBOM erfasst die Familie je Asset, und [PQ]probe erzeugt dieses Inventar aus Code, Konfiguration und Netzwerkbelegen, sodass die Abfrage Minuten dauert. Ein Team, das sie nicht ausführen kann, hat keine Messung seiner Exposition gegenüber dieser Art von Ereignis.

Die schwierigere Frage ist der Aufwand, die Antwort zu ändern: wie lange ein Austausch dauert und was er unterbricht. Algorithmenauswahlen haben sich in diesem Jahr bereits verschoben, wie der HAWK-Rückzug auf der Signaturseite gezeigt hat, und sie werden sich wieder verschieben. Migrationsdauer und Austauschaufwand sind die Zahlen, die durch jedes dieser Ereignisse hindurch zu verfolgen sind, und beide müssen weit unter ihren heutigen Stand fallen, denn Veränderungen dieser Art werden sich für den Rest des Übergangs wiederholen. Das Urteil über den Beweis ändert daran nichts.

Quellen: