Post-Quantum Security of Block Cipher Constructions

Titel: Post-Quantum Security of Block Cipher Constructions

Auteurs: Gorjan Alagic, Chen Bai, Christian Majenz, en Kaiyan Shi.

1. Het Probleem

Hoewel de impact van quantumcomputers op publieke-sleutelcryptografie (bijv. door Shor's algoritme) goed onderzocht is, blijft de post-quantum beveiliging van symmetrische cryptografie, en specifiek blokcijfers, een grotendeels onontgonnen terrein.

• Huidige situatie: Er zijn geen bekende dramatische quantum-aanvallen op momenteel ingezette symmetrische schema's, maar de theoretische onderbouwing ontbreekt.
• Gevaren: Bestaande bewijstechnieken voor klassieke beveiliging vertalen niet direct naar het quantum-domein. Adversairs met een quantumcomputer kunnen de interne circuits van een blokcijfer (zoals AES) in superpositie uitvoeren.
• Model: Het artikel richt zich op het Quantum Ideal Cipher Model (QICM). In dit model heeft de adversary quantum-toegang tot het ideale blokcijfer (via unitaire operatoren $|k\rangle|x\rangle|y\rangle \to |k\rangle|x\rangle|y \oplus \pi_k(x)\rangle$), maar de constructies die het geheimhoudende sleutel gebruiken (zoals een disk encryptie scheme), zijn klassiek toegankelijk. Dit staat bekend als het Q1-model, wat realistischer is dan het Q2-model (waar alles quantum is).

2. Methodologie

De auteurs ontwikkelen een nieuw raamwerk om post-quantum beveiliging te bewijzen voor blokcijferconstructies. De kern van hun methode bestaat uit twee onderdelen:

1. Ideal Cipher Resampling Lemma:

   • Bestaande "reprogramming" lemmata (zoals die van Zhandry) werken voornamelijk voor willekeurige functies, maar zijn moeilijk toe te passen op permutaties en ideale cijfers.
   • De auteurs bewijzen een nieuw Resampling Lemma specifiek voor het ideale cijfermodel. Dit lemma stelt dat een quantum-adversary geen wijzigingen in het ideale cijfer kan detecteren (bijvoorbeeld tijdens een simulatie in een bewijs), tenzij hij een zeer groot aantal quantum-query's heeft gedaan voordat de wijziging plaatsvond.
   • Dit lemma maakt het mogelijk om de "hybride" techniek toe te passen: het stapsgewijs vervangen van een realistisch scenario door een ideaal scenario, terwijl men de kans op detectie door de adversary onder controle houdt.

2. Hybride Bewijstechniek:

   • De auteurs passen een aangepaste versie van de hybride techniek toe (geïnspireerd door Alagic et al. [ABKM22]). Ze analyseren de onderscheidingskans tussen een "reële" wereld (met een blokcijfer) en een "ideale" wereld (met een willekeurige permutatie).
   • Door het resampling lemma te combineren met hybride argumenten, kunnen ze de beveiliging van complexe constructies afleiden zonder dat de adversary de geheime sleutel kan extraheren tijdens het bewijs.

3. Belangrijkste Bijdragen en Resultaten

Het artikel biedt de eerste rigoureuze post-quantum beveiligingsbewijzen voor een breed scala aan veelgebruikte constructies:

A. FX-constructie (Key-Length Extension)

• Constructie: FX verlengt de sleutel van een blokcijfer $E$ door witwas-sleutels toe te passen: $FX(x) = E_{k_0}(x \oplus k_1) \oplus k_2$.
• Resultaat: De auteurs bewijzen dat FX post-quantum veilig is in het QICM.
• Scherpte: De afgeleide bovengrens voor het aantal query's dat nodig is om een constante onderscheidingskans te bereiken, is strak (tight).
  • Voor kleine $q_C$ (klassieke query's) en $q_C \approx 2^n$ (volledige codebook) komt de grens overeen met Grover's zoekalgoritme.
  • Voor $q_C \approx 2^{n/3}$ komt de grens overeen met de BHT (Brassard-Høyer-Tapp) botsingszoekalgoritme.
• Toepassing: Dit bewijs de post-quantum beveiliging van lichte cijfers zoals PRINCE en PRIDE.

B. Tweakable Block Ciphers (LRW en XEX2)

• Constructies: LRW en XEX2 zijn veelgebruikte tweakable blokcijfers (XEX2 is de basis van XTS-AES voor schijfencryptie).
• Resultaat: Bewijzen voor zowel het klassieke model als het QICM.
• Grenzen: De beveiligingsgrens bevat een extra term ($6q_C^2 \cdot 2^{-n}$) die correspondeert met klassieke botsingsaanvallen die specifiek mogelijk zijn voor LRW (maar niet voor FX). Voor XEX2 is de grens $q_Q^2 \cdot 2^{-m} + 3q_C^2 \cdot 2^{-n}$.
• Significantie: Dit bevestigt dat XTS-AES (gebruikt in besturingssystemen) post-quantum veilig is, mits de parameters correct worden gekozen.

C. Algemene Stelling voor Blokcijfer Modi

• De auteurs formuleren een General Lifting Theorem (Stelling 7 en 8).
• Kern: De post-quantum beveiliging van een constructie $Con$ die een blokcijfer $E$ gebruikt, wordt begrensd door de post-quantum beveiliging van $E$ zelf plus een klassieke, informatie-theoretische grens van de constructie.
  $$Adv_{Con}^{PQ} \leq Adv_{E}^{SPRP-PQ} + \delta(q)$$
• Toepassing: Dit theorem maakt het mogelijk om de beveiliging van standaard modi zoals CBC, ECBC, CMAC, GCM en GCM-SST direct over te dragen naar het post-quantum domein. De beveiliging hangt primair af van de onderliggende blokcijferbeveiliging (die nu kwantitatief wordt bepaald door $q_Q^2/2^m$).

4. Technische Details van de Bewijzen

• Resampling Lemma (Lemma 2): Dit lemma toont aan dat als een adversary $q$ query's doet in fase 1, en er later een "swap" plaatsvindt in het ideale cijfer op basis van een verdeling $M$, de kans dat de adversary dit merkt begrensd is door $4\sqrt{q \cdot 2^n \cdot \epsilon}$, waarbij $\epsilon$ de maximale waarschijnlijkheid van de verdeling is.
• Hybride Stappen: Voor FX en LRW worden hybriden geïntroduceerd waarbij klassieke query's één voor één worden vervangen door antwoorden van een willekeurige permutatie, terwijl het onderliggende ideale cijfer lokaal wordt aangepast om consistent te blijven met de transcripten. Het resampling lemma garandeert dat de adversary deze lokale wijzigingen niet kan detecteren via zijn quantum-query's.

5. Betekenis en Conclusie

Dit werk zet de fundamenten voor een rigoureuze theorie van post-quantum beveiliging voor symmetrische cryptografie.

• Praktische Impact: Het biedt vertrouwen dat veelgebruikte standaarden (zoals AES in GCM, XTS-AES, en lichte cijfers zoals PRINCE) veilig blijven tegen quantum-adversairs, mits de sleutellengtes worden aangepast (vaak verdubbeld of verhoogd om Grover's algoritme te compenseren).
• Theoretische Vooruitgang: Het overbrugt de kloof tussen klassieke bewijstechnieken en het quantum-domein voor ideale cijfers, een gebied waarvoor eerder geen geschikte methoden bestonden.
• Parameterkeuze: De paper levert scherpe grenzen die helpen bij het bepalen van de vereiste sleutellengtes en blokgroottes voor toekomstige quantum-resistente systemen, en weerlegt het idee dat het simpelweg "verdubbelen" van de sleutellengte altijd voldoende of noodzakelijk is (afhankelijk van de constructie en het type aanval).

Kortom, de auteurs hebben bewezen dat de basis van moderne symmetrische cryptografie robuust is tegen quantum-aanvallen, mits de onderliggende blokcijfers voldoende sterk zijn en de constructies correct worden geanalyseerd binnen het QICM.