Die Dihedral-Coset-Behauptung ist widerlegt

16. August 2026

EN | DE

Der behauptete quantenpolynomielle Algorithmus für das Dihedral Coset Problem ist widerlegt. Aparna Gupte (MIT), Seyoon Ragavan (Google Quantum AI und MIT) sowie Mark Zhandry (Google Quantum AI und Stanford) haben ePrint 2026/1693 veröffentlicht, einen formalen Beweis dafür, dass der Algorithmus aus ePrint 2026/1591 das anvisierte Geheimnis nicht gewinnen kann. Die Autoren sagen ausdrücklich, dass dies über das Auffinden eines Fehlers in der ursprünglichen Analyse hinausgeht. Sie zeigen, dass der Algorithmus selbst nicht funktionieren kann, unabhängig davon, wie man ihn analysiert.

Als die Behauptung erschien, haben wir sie als ungeprüft eingestuft und argumentiert, dass die operative Schlussfolgerung in beide Richtungen gilt: Organisationen brauchen ein kryptographisches Inventar und die Fähigkeit, Algorithmen zu vertretbaren Kosten zu wechseln, denn Ergebnisse dieser Art werden weiter eintreffen. Die Widerlegung klärt diesen Einzelfall und liefert Details, die zu verstehen sich lohnt.

Was die Widerlegung zeigt

Das Dihedral Coset Problem ist wegen einer Reduktion von Oded Regev aus dem Jahr 2004 (SIAM Journal on Computing) von Bedeutung: Ein effizienter Quantenalgorithmus dafür würde effiziente Quantenalgorithmen für die Gitterprobleme liefern, die ML-KEM und ML-DSA zugrunde liegen. Regevs eigenes Verfahren erzeugt einen Quantenzustand samt klassischer Messmarken, und es braucht ein Subset-Sum-Orakel, das diese Marken vollständig verarbeitet, um zum Ziel zu kommen. Niemand weiß, wie sich dieses Orakel effizient bauen lässt. Der behauptete Algorithmus folgte Regevs ersten Schritten und schlug dann einen anderen Weg ein, der nur eine kleine Zusammenfassung der Marken nutzte.

Die Widerlegung beweist, dass dieser andere Weg versperrt ist. Ihr Hauptsatz besagt, dass jeder Algorithmus, der statt der vollständigen Marken nur einen kleinen Auszug jeder klassischen Marke behält, das Zielbit des Geheimnisses höchstens mit einem exponentiell kleinen Vorteil gegenüber blindem Raten erraten kann. Schon etwas mehr als eine logarithmische Anzahl verworfener Bits pro Marke genügt, um das Geheimnis zu verbergen. Das Ergebnis ist informationstheoretisch, das heißt, die zurückbehaltenen Daten enthalten das Geheimnis überhaupt nicht mehr. Keine spätere Berechnung, wie raffiniert auch immer, kann Information wiedergewinnen, die in ihrer Eingabe fehlt.

Der behauptete Algorithmus fällt unter diesen Satz, weil sich seine Zusammenfassungen bis auf vernachlässigbaren Fehler aus etwa dem obersten Drittel der Bits jeder Marke rekonstruieren lassen. Die Autoren schließen auch die verfahrenstechnischen Auswege. Die Messung der Marken bis zum Schluss aufzuschieben ändert nichts, weil die Messung an den Anfang kommutiert. Das Verfahren zu wiederholen, um einen winzigen Vorteil zu verstärken, scheitert an einem Kostenargument: Entweder bleibt der Ratevorteil am Ende exponentiell klein, oder die erwartete Zahl der Wiederholungen wächst exponentiell.

Was offen bleibt

Der Satz schränkt eine Familie von Ansätzen ein. Er besagt, dass jeder Algorithmus, der Regevs Vorlage folgt, die vollständigen klassischen Marken in seiner Schlussphase wesentlich nutzen muss. Er beweist nicht, dass das Dihedral Coset Problem schwer ist, und er beweist nicht, dass Gitterprobleme schwer sind. Die Autoren schreiben, dass Varianten den formalen Rahmen ihres Satzes verlassen könnten, sie erwarten aber, dass solche Varianten aus demselben zugrunde liegenden Grund scheitern, und sie kennen keine plausible Reparatur.

Als strukturelles Ergebnis gelesen, spricht dies für die gitterbasierten Standards. Der bekannte Weg über diese Vorlage verlangt genau die Ressource, ein Subset-Sum-Orakel über die vollständigen Marken, die sich seit 2004 einer effizienten Konstruktion entzieht. Zuversicht dieser Art ist selten und verdient eine genaue Einordnung: Eine Klasse von Angriffen ist jetzt beweisbar ausgeschlossen, und die allgemeine Frage bleibt offen.

Wie es geprüft wurde

Die Behauptung wurde am 31. Juli veröffentlicht, und die Widerlegung bezieht sich auf ihre Überarbeitung vom 11. August. Die Widerlegung folgte innerhalb weniger Tage auf diese Überarbeitung und erscheint mit einer Lean-4-Formalisierung, maschinenprüfbarem Code, der die Hauptergebnisse verifiziert. Die Danksagung dankt Daniel R. Simon, dem ursprünglichen Autor, für die Gespräche, die Prüfung fand also mit seiner Beteiligung statt und nicht an ihm vorbei. Seyoon Ragavan, ein Mitautor der Widerlegung, steht in der Danksagung des ursprünglichen Entwurfs und ist eine seiner beiden persönlichen Mitteilungen als Quelle, also genau dort, wo wir die Prüfung am ehesten erwartet hatten. Die Autoren legen zudem offen, dass der verallgemeinerte Satz im Gespräch mit einem KI-Modell entstanden ist und dass dieselben Werkzeuge die Formalisierung erzeugt haben, wobei die Autoren für die Korrektheit einstehen. Die Prüfzyklen für kryptographische Behauptungen werden schneller, und maschinengeprüfte Beweise werden Teil davon, wie solche Auseinandersetzungen enden.

Die operative Lesart

Zwischen der Behauptung und der Widerlegung lag ein Fenster von mehreren Tagen, in dem die verantwortliche Frage für ein Sicherheitsteam eine Frage des Umfangs war: Welche unserer Assets stützen sich auf Gitterannahmen als ihren einzigen Post-Quanten-Schutz. Diese Frage zu beantworten verlangt ein Inventar der ausgerollten Kryptographie, das sich nach Algorithmenfamilie abfragen lässt. Ein CBOM im Format CycloneDX 1.6 unterstützt genau diese Abfrage, und [PQ]probe erzeugt eines bei jedem Scan.

Die Schlussfolgerung aus dem ersten Beitrag bleibt vom Ausgang unberührt. Der Prüfzyklus für diese Behauptung lief in Tagen, während Algorithmenmigrationen in Jahren laufen, die Planung muss also davon ausgehen, dass weitere solche Behauptungen eintreffen, und sie kann nicht innehalten, bis sich jede einzelne klärt. Am besten aufgestellt waren in diesem Fenster die Organisationen, die die Frage nach dem Umfang noch am Tag der Veröffentlichung beantworten konnten.

Quellen:

← Alle [PQ]files