Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768 at the Heuristic Failure Scale

In der digitalen Welt beruht Sicherheit oft auf mathematischen Problemen, die in eine Richtung leicht zu verwenden, aber ohne die richtigen geheimen Informationen extrem schwierig umzukehren sind. ML-KEM ist ein Post-Quanten-Schlüsselaustauschmechanismus, der darauf ausgelegt ist, selbst gegen zukünftige Quantencomputer sicher zu bleiben. Wie andere gitterbasierte kryptografische Systeme hat es eine extrem geringe Wahrscheinlichkeit für das sogenannte ehrliche Dekapsulierungsversagen: Selbst wenn sich beide Parteien korrekt verhalten, könnten die beiden Seiten im Prinzip unterschiedliche Schlüssel ableiten. Zu schätzen, wie selten dies vorkommen kann, ist eine wichtige Frage der Korrektheit. Bisherige Analysen haben sich weitgehend auf heuristische Schätzungen des Fehlerskalen-Ausmaßes verlassen, während das Erreichen einer strengen Schranke, die die relevanten mathematischen Abhängigkeiten zwischen den verschiedenen Fehlertermen bewahrt, wesentlich schwieriger ist.

Eine neue Studie von Aurélie Duriez und Christophe Tommasini geht dieses Problem an, indem sie eine rigorose mathematische Analyse von ML-KEM-768 innerhalb einer expliziten idealisierten Zufallsfunktion / Centered-Binomial-Abstraktion (ROM/CBD) entwickelt. Die Arbeit ist keine Simulation und versucht nicht, die exakte Fehlerrate zu berechnen. Stattdessen leiten die Autoren eine zertifizierte obere Schranke für die Wahrscheinlichkeit eines ehrlichen Dekapsulierungsfehlers ab, während sie die wichtigen Abhängigkeiten zwischen den verschiedenen Fehlertermen beibehalten. Insbesondere berücksichtigt die Analyse die Abhängigkeiten, die durch die öffentliche Matrix und durch beide Ciphertext-Kompressionsbegriffe induziert werden, anstatt sie einfach als unabhängig zu behandeln. Die resultierende zertifizierte obere Schranke ist kleiner als eins zu 2 hoch 164,81.

Dieser Befund ist signifikant, da er eine heuristische Schätzung der Fehlerskala innerhalb des untersuchten expliziten Modells durch eine abhängigkeitsbewusste, zertifizierte obere Schranke ersetzt. Die Analyse nimmt nicht einfach an, dass die relevanten Fehler unabhängig sind; sie bewahrt die mathematischen Abhängigkeiten, die zwischen ihnen entstehen. Die zertifizierte Schranke erreicht im Wesentlichen dieselbe Größenordnung wie frühere heuristische Schätzungen, dies sollte jedoch nicht so interpretiert werden, dass damit bewiesen wird, dass diese Schätzungen die exakte Fehlerrate darstellen. Das Ergebnis ist bewusst enger gefasst: Innerhalb der im Papier untersuchten expliziten ROM/CBD-Abstraktion ist die Wahrscheinlichkeit eines ehrlichen Dekapsulierungsfehlers rigoros nach oben begrenzt. Das Papier stellt auch klar, dass dies keine exakte Dekapsulierungsfehlerrate ist und keine informationstheoretische Aussage über die feste SHAKE-Instanziierung von FIPS 203 darstellt.

Die Arbeit erforderte eine andere Herangehensweise an das Problem. Vereinfachte heuristische Analysen können viel einfacher werden, wenn einige Fehlerterme als unabhängig behandelt werden, aber die tatsächliche algebraische Struktur erzeugt Abhängigkeiten, die eine rigorose Analyse bewahren muss. Die Autoren entwickelten daher eine Methode, die diese Abhängigkeiten durch die Berechnung verfolgt, anstatt sie zu verwerfen. Der Forschungsprozess nutzte zudem eine KI-gestützte Methodik, um potenzielle Ansätze zu untersuchen, kritische Fälle zu identifizieren und die Analyse zu strukturieren. Dieser explorative Einsatz von KI wurde mit erschöpfenden, computerverifizierten Prüfungen, exakter oder zertifizierter Arithmetik und unabhängig überprüfbaren Berechnungen kombiniert, um die schwierigsten Teile des Arguments zu schließen. Die endgültigen mathematischen Behauptungen beruhen daher auf expliziten, reproduzierbaren Belegen und nicht auf dem KI-Output selbst.

Das Ergebnis ist eine rigorose und transparente, zertifizierte Korrektheitsgrenze innerhalb der genannten Abstraktion. Die Forscher haben ihren Code, ihre Daten und die unterstützenden Artefakte zur Verfügung gestellt, damit die Berechnungen unabhängig überprüft werden können. Diese Reproduzierbarkeit ist in der Kryptografie besonders wichtig, in der mathematische Behauptungen einer unabhängigen Verifizierung offenstehen sollten. Die Studie zeigt, dass innerhalb der betrachteten expliziten ROM/CBD-Abstraktion die Wahrscheinlichkeit eines ehrlichen Dekapsulierungsfehlers auf einem extrem niedrigen Niveau begrenzt ist. Es sollte jedoch nicht als allgemeines Sicherheitszertifikat für ML-KEM-768 interpretiert werden, nicht als Beweis für alle Sicherheitseigenschaften des standardisierten Schemas und nicht als eine Aussage, die jede Hardware- oder Softwareimplementierung abdeckt.

Dieses Ergebnis erweitert das rigorose Verständnis eines spezifischen Aspekts der Korrektheit von ML-KEM-768, indem es von einer heuristischen Fehlerskalen-Schätzung zu einer abhängigkeitsbewussten, zertifizierten oberen Schranke innerhalb einer klar definierten Abstraktion übergeht. Es zeigt, dass eine Schranke auf der heuristischen Skala etabliert werden kann, während gleichzeitig wichtige Abhängigkeiten zwischen den relevanten Fehlertermen gewahrt bleiben. Die Zahl 164,81 ist der zertifizierte Exponent dieser oberen Schranke: Innerhalb der genannten ROM/CBD-Abstraktion ist die Wahrscheinlichkeit eines ehrlichen Dekapsulierungsfehlers nach oben durch 2 hoch -164,81 begrenzt. Diese Zahl sollte daher als eine präzise Eigenschaft der im Papier bewiesenen zertifizierten Schranke verstanden werden und nicht als allgemeines Maß für die Sicherheit oder Zuverlässigkeit von ML-KEM-768 als Ganzes.

Die Forscher haben auch darauf geachtet, die Grenzen ihrer Arbeit zu erläutern. Sie merkten an, dass ihr Beweis für eine spezifische Abstraktion des Systems gilt und nicht notwendigerweise für jede mögliche Implementierung der Software. Sie behaupteten nicht, das Problem für alle Variationen des Verschlüsselungsstandards gelöst zu haben, noch deuteten sie an, dass das System gegen alle Arten von Angriffen immun sei. Ihr Fokus lag strikt auf der Korrektheit des Entschlüsselungsprozesses unter ehrlichen Bedingungen. Indem sie klar darüber waren, was sie bewiesen haben und was nicht, stellten sie sicher, dass ihre Ergebnisse nicht missverstanden werden. Die Studie steht als Zeugnis für die Kraft einer sorgfältigen, detaillierten Analyse in einem Bereich, in dem kleine Fehler enorme Konsequenzen haben können. Sie zeigt, dass mit genügend Rigor und den richtigen Werkzeugen selbst die komplexesten mathematischen Systeme verstanden und verifiziert werden können.

Am Ende liefert das Papier ein präzises, aber bewusst eingegrenztes Ergebnis: Innerhalb der genannten ROM/CBD-Abstraktion ist die Wahrscheinlichkeit eines ehrlichen Dekapsulierungsfehlers rigoros nach oben durch 2 hoch -164,81 begrenzt. Dies ist eine extrem kleine zertifizierte obere Schranke, aber es ist keine exakte Fehlerrate und es ist kein pauschaler Beweis dafür, dass das vollständig eingesetzte ML-KEM-768-System unter allen realen Bedingungen ohne Fehler funktioniert. Der Beitrag liegt darin, eine heuristische Fehlerskalen-Schätzung durch eine abhängigkeitsbewusste, reproduzierbare und unabhängig überprüfbare Schranke innerhalb eines klar definierten Modells zu ersetzen. Seine Stärke liegt nicht darin, Gewissheit jenseits dieses Modells zu beanspruchen, sondern darin, explizit zu sein darüber, was bewiesen wurde und was außerhalb des Geltungsbereichs des Ergebnisses liegt.