Simons Quantenalgorithmus für das Dihedral-Coset-Problem: Was an der Behauptung dran ist

Was Simon konkret behauptet

Das DCP gilt seit Langem als möglicher Verbindungspunkt zwischen Quantenalgorithmen und gitterbasierten Problemen. Simons zentrale Aussagen sind:

• DCP in Polynomialzeit: Sein Verfahren soll das Dihedral-Coset-Problem auf einem Quantencomputer mit polynomialem Aufwand lösen. Es baut dabei auf einer Reduktion von Oded Regev aus dem Jahr 2002 auf, die das Dihedral-Subgruppenproblem mit dem DCP verbindet .
• Schließen einer jahrzehntealten Lücke: Regevs Arbeiten stellten eine Verbindung zu Gitterproblemen her, ließen aber die entscheidende algorithmische Lücke offen. Diese besteht seit ungefähr 2004 .
• Neuer technischer Ansatz: Simon ersetzt ein zentrales Orakel früherer Ansätze durch eine sogenannte „Block-and-Query“-Methode, mit der sich Informationen über die verborgene Untergruppe gewinnen lassen sollen .
• Mögliche Folgen für Gitterprobleme: Nach Darstellung des Preprints könnte sich der Algorithmus mit Reduktionen von Regev sowie späteren Verbesserungen von Brakerski, Kirshanova, Stehlé und Wen kombinieren lassen. Genannt werden unter anderem Polynomialzeit-Algorithmen für eine polynomiale Approximation des kürzesten Vektors (SVP) und für Learning With Errors (LWE) .

Das Verfahren soll außerdem eine fehlerhafte beziehungsweise unbrauchbare Stichprobenrate von bis zu 1/O(log n) tolerieren. Diese Eigenschaft wäre wichtig, damit sich der Algorithmus mit dem bestehenden Reduktionsweg zu Gitterproblemen verbinden lässt .

Warum die Fachwelt noch abwartet

Der entscheidende Punkt ist derzeit nicht die Tragweite der Behauptung, sondern die Frage, ob der Beweis einer unabhängigen Prüfung standhält.

• Noch kein Peer-Review: Der Entwurf trägt ausdrücklich die Bezeichnung „Preliminary Draft“. Er wurde weder in einer Fachzeitschrift noch auf einer Konferenz begutachtet und veröffentlicht .
• Zentrale Beweise nur skizziert: Frühe Analysen weisen darauf hin, dass mehrere tragende Argumente lediglich in Beweis-Skizzen vorliegen. Auch die abschließenden Aussagen zu SVP- und LWE-Parametern stützen sich teilweise auf unveröffentlichte persönliche Mitteilungen statt auf vollständig dokumentierte Herleitungen .
• Keine unabhängige Bestätigung: Bis zum 7. und 8. August 2026 wurde weder eine unabhängige Bestätigung noch eine endgültige Widerlegung veröffentlicht . Die vorherrschende Haltung lautet daher: erst prüfen, dann bewerten.
• Kein praktischer Angriff: Das Preprint ist ein theoretisches Ergebnis zum DCP. Es enthält keine implementierte Attacke auf ML-KEM, ML-DSA oder ein anderes standardisiertes Kryptosystem .

Die in ersten Reaktionen berichtete „starke Skepsis“ richtet sich damit vor allem auf die Beweisführung – nicht darauf, dass die Fragestellung irrelevant wäre .

Was bedeutet das für ML-KEM und ML-DSA?

Für Organisationen, die derzeit Post-Quantum-Kryptografie einführen oder bewerten, ist die kurzfristige Antwort relativ eindeutig: Auf Grundlage dieses Preprints muss die Migrations- oder Einsatzplanung nicht geändert werden .

Keine direkte Attacke auf NIST-Standards

ML-KEM nach FIPS 203 und ML-DSA nach FIPS 204 werden in der Arbeit nicht angegriffen. Auch wurde kein NIST-Parametersatz kompromittiert . Ein Algorithmus für das allgemeine DCP ist nicht automatisch ein Verfahren, mit dem sich aus realen ML-KEM- oder ML-DSA-Schlüsseln geheime Informationen gewinnen lassen.

Die Verbindung ist theoretisch und mehrstufig

Das DCP ist über bekannte Reduktionen mit Gitterproblemen verknüpft. Daraus folgt jedoch nicht unmittelbar ein konkreter Angriff auf Module-LWE oder Module-SIS – die spezifischen Härteannahmen, auf denen ML-KEM beziehungsweise ML-DSA beruhen . Dafür müsste zusätzlich gezeigt werden, dass der gesamte Reduktionsweg für die in den Standards verwendeten strukturierten Gitterinstanzen praktisch und mit relevanten Parametern funktioniert.

Genau hier liegt der Unterschied zwischen einer wichtigen theoretischen Warnung und einer gebrochenen Verschlüsselung: „Gitterprobleme“ sind eine breite Problemklasse. Die NIST-Standards verwenden jedoch bestimmte strukturierte Varianten und konkrete Parameter .

Einordnung früherer Ergebnisse

Die Entwicklung kommt nicht völlig aus dem Nichts. Bai, Jangir, Kirshanova, Ngo und Youmans beschrieben 2025 einen Quantenalgorithmus mit quasipolynomialer Laufzeit für eine eingeschränkte DCP-Variante, das extrapolierte DCP über Moduli, die Zweierpotenzen sind . Ein vollständiger Polynomialzeit-Algorithmus für das DCP wäre gegenüber diesem Ergebnis ein erheblicher Sprung – sofern sich Simons Beweis als korrekt erweist.

Die möglichen Folgen – falls die Behauptung bestätigt wird

Eine Bestätigung würde die theoretische Einschätzung verändern, wie schwer bestimmte Gitterprobleme für Quantencomputer sind. Sie könnte insbesondere den Eindruck stärken, dass sich ausgewählte Gitteraufgaben mit Quantenverfahren effizient lösen lassen .

Die Konsequenzen für die praktische Post-Quantum-Kryptografie wären aber weiterhin von zusätzlichen Nachweisen abhängig:

1. Der DCP-Algorithmus selbst müsste vollständig validiert werden.
2. Die verwendeten Reduktionen müssten für die relevanten Gittervarianten nachvollziehbar und effizient sein.
3. Es müsste ein konkreter Zusammenhang zu den strukturierten Annahmen von ML-KEM und ML-DSA hergestellt werden.
4. Schließlich wären Ressourcenbedarf, Fehlerkorrektur und Skalierbarkeit auf realistischen Quantencomputern zu bewerten.

Auch ein korrekter Polynomialzeit-Algorithmus wäre daher nicht automatisch gleichbedeutend mit einem sofort nutzbaren Angriff auf heutige Kommunikationssysteme.

Vorläufiges Fazit: wichtig, aber kein Grund zur Panik

Simons Preprint ist eine außergewöhnlich weitreichende theoretische Behauptung. Gelingt die unabhängige Prüfung, könnte es eine seit rund zwei Jahrzehnten bestehende Lücke zwischen dem Dihedral-Coset-Problem und bestimmten Gitterproblemen schließen .

Der aktuelle Stand ist jedoch deutlich nüchterner: Das Dokument ist ein ungeprüfter vorläufiger Entwurf, mehrere zentrale Beweise sind nur skizziert, und unabhängige Reproduktionen liegen noch nicht vor . Es gibt weder eine veröffentlichte Attacke auf ML-KEM oder ML-DSA noch einen gebrochenen NIST-Parametersatz .

Für die Praxis lautet die angemessene Reaktion deshalb nicht „alles ist sicher“, aber ebenso wenig „die Post-Quantum-Kryptografie ist gebrochen“: Beweis prüfen, Konsequenzen im Detail analysieren und die laufende Migration nicht aufgrund einer einzelnen, bislang unbestätigten Behauptung stoppen.