Post-Quantum Security of Block Cipher Constructions

1. Problemstellung

Blockchiffren sind fundamentale Bausteine der modernen Kryptographie (z. B. AES) und werden in einer Vielzahl von Anwendungen eingesetzt, von sicheren Internetkommunikationen bis hin zur Festplattenverschlüsselung. Während die post-quantum-Sicherheit von Public-Key-Verfahren (z. B. durch Shor-Algorithmus bedroht) intensiv untersucht wurde, ist die Sicherheit symmetrischer Verfahren (Blockchiffren) gegenüber Quantenangriffen weniger erforscht.

Das Hauptproblem besteht darin, dass etablierte Sicherheitsbeweise für symmetrische Kryptographie oft auf klassischen Annahmen basieren (z. B. Transkripte von Abfragen), die sich nicht direkt auf das Quantenmodell übertragen lassen. Zudem ist unklar, ob die gängige Praxis, die Schlüssellänge einfach zu verdoppeln, ausreicht, um Angriffe wie Grovers Suchalgorithmus zu verhindern. Es fehlt an rigorosen Sicherheitsbeweisen für gängige Konstruktionen (wie FX, LRW, XEX und Betriebsmodi) im Quantum Ideal Cipher Model (QICM). In diesem Modell kann ein Angreifer den zugrundeliegenden idealen Blockchiffren-Orakel in Superposition abfragen, während die Konstruktion selbst (die den geheimen Schlüssel verwendet) klassisch bleibt.

2. Methodik

Die Autoren entwickeln eine neue technische Grundlage für Sicherheitsbeweise im QICM, die auf einer Kombination aus hybriden Argumenten und einem neuartigen Resampling-Lemma für ideale Chiffren basiert.

• Hybride Argumente (Hybrid Technique): Um die Ununterscheidbarkeit zwischen einer realen Konstruktion und einem idealen Zufallsorakel zu zeigen, wird eine Sequenz von hybriden Experimenten konstruiert. Dabei werden klassische Abfragen schrittweise durch ideale Zufallsantworten ersetzt.
• Das Resampling-Lemma für Ideale Chiffren: Ein zentrales technisches Hindernis bei hybriden Beweisen im Quantenkontext ist, dass ein Quantenangreifer durch Abfragen den Schlüssel extrahieren könnte, bevor eine Änderung im Orakel (Resampling) erfolgt. Um dies zu umgehen, modifizieren die Autoren das ideale Orakel $E$ an wenigen Stellen (Resampling), um die Konsistenz mit den bisherigen Abfragen zu gewährleisten, und setzen diese Änderungen später zurück.
  • Das neue Lemma zeigt, dass ein Angreifer diese Modifikationen nicht erkennen kann, es sei denn, er hat eine sehr große Anzahl von Quantenabfragen vor der Modifikation durchgeführt. Dies bricht den Zirkelschluss, der bei klassischen Beweisen oft auftritt.
• Modellannahmen: Die Arbeit betrachtet das Q1-Modell (auch post-quantum-Modell genannt), in dem der Angreifer Quantenzugriff auf den öffentlichen idealen Blockchiffren hat, aber nur klassischen Zugriff auf die Konstruktion, die den geheimen Schlüssel verwendet. Dies ist das realistischste Modell für aktuelle Anwendungen.

3. Wichtige Beiträge

Die paper liefert die ersten vollständigen post-quantum-Sicherheitsbeweise für mehrere kritische Konstruktionen:

1. FX-Konstruktion (Schlüssellängenerweiterung):

   • Beweis der Sicherheit der FX-Konstruktion (die einen Blockchiffren in eine längere Schlüssellänge umwandelt) im QICM.
   • Die bewiesene Obergrenze für den Unterscheidungsfehler ist tight (scharf). Sie stimmt mit den bekannten Quantenangriffen (Grover, BHT-Kollisionsfindung, Offline-Simon) überein.
   • Anwendung auf leichte Chiffren wie PRINCE und PRIDE.

2. Tweakable Blockchiffren (LRW und XEX2):

   • Sicherheitsbeweise für die weit verbreiteten tweakable Blockchiffren LRW und XEX2 (die Basis für XTS-AES, den Standard für Festplattenverschlüsselung).
   • Die Beweise gelten sowohl im klassischen Modell als auch im QICM.
   • Es wird gezeigt, dass die klassischen Kollisionsangriffe (Birthday-Attacke) auch im Quantenkontext relevant bleiben, während zusätzliche Quantenbeschleunigungen bei der Schlüsselsuche berücksichtigt werden.

3. Allgemeines Lift-Theorem für Betriebsmodi:

   • Die Autoren stellen ein allgemeines Theorem (Theorem 7 und 8) vor, das die post-quantum-Sicherheit von Betriebsmodi (wie CBC, CTR, GCM, CMAC) auf die Sicherheit des zugrundeliegenden Blockchiffren reduziert.
   • Das Theorem besagt, dass die Sicherheit eines Modus durch die Summe aus der post-quantum-Sicherheit des idealen Chiffren (im QICM) und der klassischen informationstheoretischen Sicherheit des Modus (mit einem idealen Zufallsorakel) begrenzt ist.
   • Dies ermöglicht eine einfache Übertragung klassischer Sicherheitsgrenzen auf das Quantenregime.

4. Ergebnisse und Sicherheitsgrenzen

Die Arbeit liefert präzise mathematische Grenzen für den Vorteil eines Angreifers ($Adv$) in Abhängigkeit von der Anzahl der klassischen Abfragen ($q_C$) und Quantenabfragen ($q_Q$):

• FX-Konstruktion:
  $$Adv \lesssim (q_C \sqrt{q_Q} + q_Q \sqrt{q_C}) \cdot 2^{-(m+n)/2}$$
  Dies zeigt, dass für eine konstante Erfolgswahrscheinlichkeit die Komplexität der Angriffe (z. B. Offline-Simon) exakt durch diese Grenzen vorhergesagt wird.

• LRW / XEX2:
  Die Grenzen enthalten Terme wie $q_C^2 \cdot 2^{-n}$ (klassische Kollisionen) und Terme, die die Quanten-Schlüsselsuche widerspiegeln. Für LRW im QICM ergibt sich beispielsweise:
  $$Adv \lesssim \frac{q_Q^2}{2^m} + \frac{q_C^2}{2^n}$$
  (unter Vernachlässigung von Konstanten und spezifischen Hybrid-Terminen).

• Betriebsmodi:
  Für Modi wie GCM oder CBC wird gezeigt, dass die post-quantum-Sicherheit durch $O(q_Q^2 / 2^m)$ (Quanten-Suche nach dem Schlüssel) und $O(q_C^2 / 2^n)$ (klassische Kollisionen im Modus) begrenzt ist.

5. Bedeutung und Fazit

Diese Arbeit legt den Grundstein für eine rigorose Theorie der post-quantum-Sicherheit symmetrischer Kryptographie.

• Praktische Relevanz: Da die meisten aktuellen Systeme (Internet, Festplattenverschlüsselung) auf Blockchiffren und deren Modi basieren, ist die Bestätigung ihrer Sicherheit (oder die Identifizierung notwendiger Parameteranpassungen) kritisch für den Übergang zur Post-Quantum-Ära.
• Paradigmenwechsel: Die Ergebnisse widerlegen oder präzisieren die naive Annahme, dass eine einfache Verdopplung der Schlüssellänge immer ausreicht. Die Arbeit zeigt, dass die Sicherheitsgrenzen komplexer sind und von der Interaktion zwischen klassischen und Quantenabfragen abhängen.
• Methodischer Durchbruch: Das entwickelte Resampling-Lemma für ideale Chiffren ist ein mächtiges Werkzeug, das zukünftig für die Analyse weiterer symmetrischer Konstruktionen im Quantenkontext genutzt werden kann.

Zusammenfassend beweist das Papier, dass viele etablierte symmetrische Konstruktionen auch im Quantenmodell sicher bleiben, sofern die Parameter (Schlüssellänge, Blockgröße) entsprechend den neuen, scharfen Grenzen gewählt werden, und liefert die ersten formalen Beweise für diese Behauptungen.