Sicherheitsbeweise und Reduktionen in Gitterverfahren

Ein Sicherheitsbeweis für ein kryptografisches Verfahren ist ein formales mathematisches Argument, das zeigt, dass das Brechen des Verfahrens das Lösen eines zugrunde liegenden schwierigen Problems voraussetzt. Der Beweis garantiert keine absolute Sicherheit. Er zeigt, dass sich jeder effiziente Angreifer gegen das Verfahren in einen effizienten Löser für das schwierige Problem umwandeln lässt. Wenn das schwierige Problem nicht praktikabel lösbar ist, ist das Verfahren sicher.

Regevs wegweisender Beweis von 2005 zeigt, dass ein Algorithmus mit polynomieller Laufzeit, der entscheidungsbasiertes LWE löst, zum Lösen von GapSVP (Gap-Problem des kürzesten Vektors) auf Gittern mit n Dimensionen verwendet werden kann. Die Reduktion ist quantenbasiert: Sie verwendet ein quantenmechanisches Stichprobenverfahren, um einen LWE-Löser in einen Gitterlöser umzuwandeln. Das bedeutet, dass LWE unter Quantenberechnung mindestens so schwierig ist wie Gitterprobleme im Worst Case.

Regevs Reduktion ist nicht eng: Die polynomialen Faktoren in der Reduktion bedeuten, dass das durch den Beweis garantierte Sicherheitsniveau etwas schwächer ist, als die besten bekannten Angriffe nahelegen. Für die praktische Parameterwahl verwenden Kryptografen die konkrete Sicherheit der besten bekannten Angriffe, die mithilfe des lattice estimator ermittelt wird, statt der theoretischen Schranke der Reduktion, da die Reduktion konservativ ist.

Ein auf LWE basierendes Verschlüsselungsverfahren wird mithilfe eines hybriden Arguments als IND-CPA-sicher (unterscheidbar unter einem Angriff mit gewähltem Klartext) bewiesen. Der Beweis zeigt, dass aus einem IND-CPA-Unterscheider ein LWE-Unterscheider folgt. Im ersten Hybridschritt wird der echte Chiffretext durch eine gleichverteilte Zufallszeichenkette ersetzt; die Ununterscheidbarkeit folgt aus der LWE-Annahme. Dies liefert einen klaren Sicherheitsbeweis für grundlegende gitterbasierte Verschlüsselung.

IND-CPA-Sicherheit reicht für Schlüsselverkapselungsmechanismen, die in TLS eingesetzt werden, nicht aus: Sie benötigen IND-CCA2-Sicherheit (Sicherheit gegen Angriffe mit gewähltem Chiffretext). Die Fujisaki-Okamoto-(FO-)Transformation wandelt jedes IND-CPA-Verfahren im Random-Oracle-Modell (ROM) in ein IND-CCA2-KEM um. ML-KEM wendet eine Variante der FO-Transformation auf die zugrunde liegende Module-LWE-Verschlüsselung an und bietet dadurch die für den praktischen Einsatz erforderliche CCA2-Sicherheit.

Das Random-Oracle-Modell (ROM) modelliert Hashfunktionen als wirklich zufällige Funktionen. Viele Sicherheitsbeweise, darunter auch die für die FO-Transformation, setzen das ROM voraus. In der Praxis sind Hashfunktionen wie SHA-3 keine echten Zufallsorakel, daher garantieren ROM-Beweise keine Sicherheit im Standardmodell. Dennoch werden ROM-Beweise in der Kryptografie-Community weithin als starke Sicherheitsevidenz akzeptiert.

Ein Beweis im Standardmodell nimmt keine Idealisierung von Hashfunktionen vor und ist damit strikt stärker als ein ROM-Beweis. Die meisten praktischen Gitterverfahren verwenden ROM-Beweise, weil CCA2-Beweise im Standardmodell für gitterbasierte KEMs deutlich komplexer sind und schlechtere konkrete Parameter liefern. NIST akzeptierte ROM-basierte Beweise für ML-KEM und betrachtete sie für die angestrebten Sicherheitsstufen als ausreichend.

Der Sicherheitsbeweis für ML-KEM erfolgt in zwei Schritten. Zunächst wird gezeigt, dass die zugrunde liegende Module-LWE-Verschlüsselung unter der M-LWE-Annahme IND-CPA-sicher ist. Anschließend hebt die Fujisaki-Okamoto-Transformation, genauer gesagt die in Kyber verwendeten T- und U-Transformationen, diese Sicherheit im Quanten-Random-Oracle-Modell (QROM) auf IND-CCA2 an. Dieses Modell berücksichtigt Angreifer, die das Zufallsorakel in Superposition abfragen.

Der Lattice Estimator von Albrecht, Player und Scott ist das Standardwerkzeug zur Berechnung der konkreten Sicherheit LWE-basierter Verfahren. Er modelliert die Kosten der besten bekannten Gitterangriffe, etwa BKZ mit Siebverfahren oder Enumeration, und gibt für vorgegebene Parameter (n, q, sigma) eine geschätzte Bit-Sicherheit aus. Das Werkzeug wird regelmäßig aktualisiert, sobald neue Algorithmen und Kostenmodelle für Hardware veröffentlicht werden.

Der Block-Korkine-Zolotarev-Algorithmus (BKZ) ist der beste praktische Algorithmus zur Gitterreduktion. BKZ mit einer Blockgröße beta findet kurze Vektoren mit einer Komplexität von ungefähr 2^{0.292*beta} Gatteroperationen, wenn die besten Siebalgorithmen verwendet werden. Für ML-KEM-768 wird die klassische Sicherheit auf etwa 180 Bit und die Quantensicherheit auf etwa 164 Bit geschätzt und liegt damit deutlich über dem Zielwert von 192 Bit.

Asymptotische Sicherheitsbeweise zeigen, dass ein Verfahren für hinreichend große Parameter sicher ist, legen aber nicht fest, was „hinreichend groß“ in der Praxis bedeutet. Die Analyse der konkreten Sicherheit schließt diese Lücke, indem sie die tatsächlichen Kosten des besten Angriffs für die gewählten Parameter schätzt. Die Post-Quanten-Standardisierung stützt sich stark auf Analysen der konkreten Sicherheit. Die Parameter werden so gewählt, dass sie Angriffen auf absehbare Quantenhardware über einen Zeitraum von 30 Jahren widerstehen.

Welche Transformation wird verwendet, um gitterbasierte IND-CPA-Verschlüsselung in ML-KEM auf IND-CCA2-Sicherheit anzuheben?

Sicherheitsbeweise für Gitterverfahren führen die Sicherheit des Verfahrens auf die Schwierigkeit von LWE oder SVP zurück. Regevs Reduktion garantiert, dass LWE mindestens so schwierig ist wie Gitterprobleme im Worst Case. Die Fujisaki-Okamoto-Transformation hebt IND-CPA im ROM auf IND-CCA2 an. Die konkrete Sicherheit wird mithilfe des lattice estimator und BKZ-Komplexitätsmodellen bewertet. Lücken bei der Reduktionsschärfe führen dazu, dass sich die praktischen Parameter eher auf Schätzungen der Angriffskosten als allein auf Reduktionsschranken stützen.