Post-Quantum Security of Block Cipher Constructions

1. Il Problema

La sicurezza della crittografia a chiave pubblica è stata ampiamente analizzata alla luce della computazione quantistica (principalmente a causa dell'algoritmo di Shor). Tuttavia, la sicurezza post-quantum della crittografia a chiave simmetrica, e in particolare dei cifrari a blocchi (come AES) e delle loro costruzioni derivate, rimane un'area largamente inesplorata.

Sebbene non esistano attacchi quantistici drammatici noti contro gli schemi simmetrici attualmente in uso, la mancanza di prove formali di sicurezza post-quantum e di limiti inferiori precisi (tight bounds) è problematica. I praticanti spesso assumono che raddoppiare la lunghezza della chiave sia sufficiente per mitigare l'algoritmo di Grover, ma la letteratura recente suggerisce che questa assunzione potrebbe essere talvolta eccessiva o, in alcuni casi, insufficiente. Il problema centrale è determinare come gli avversari quantistici, capaci di eseguire query in sovrapposizione su oracoli ideali (Ideal Cipher Model), influenzino la sicurezza di costruzioni complesse come l'estensione della lunghezza della chiave, i cifrari a blocchi modificabili (tweakable) e le modalità di cifratura.

2. Metodologia

Gli autori sviluppano un nuovo quadro teorico per analizzare la sicurezza post-quantum, operando principalmente nel Quantum Ideal Cipher Model (QICM). In questo modello:

• Il cifrario sottostante è trattato come un "cifrario ideale" accessibile quantisticamente (query in sovrapposizione).
• Le costruzioni che utilizzano chiavi segrete (es. il cifrario stesso o le modalità di cifratura) sono accessibili solo classicamente dall'avversario (modello Q1).

La metodologia si basa su due pilastri tecnici principali:

1. Lemma di Resampling per Cifrari Ideali (Ideal Cipher Resampling Lemma):
   Gli autori generalizzano i lemmi di "resampling" (campionamento) esistenti, che erano limitati alle funzioni casuali o permutazioni casuali, al contesto dei cifrari ideali. Questo lemma quantifica la capacità di un avversario quantistico di rilevare modifiche locali a un cifrario ideale (ad esempio, lo scambio di due valori di output per una specifica chiave). Dimostrano che un avversario non può distinguere un cifrario modificato da uno originale a meno che non abbia effettuato un numero molto elevato di query quantistiche prima della modifica. Questo strumento è fondamentale per le dimostrazioni di sicurezza tramite ibridi.

2. Tecnica Ibrida (Hybrid Technique) Adattata:
   Utilizzando il lemma di resampling, gli autori applicano una tecnica di dimostrazione ibrida. Invece di sostituire direttamente le query classiche con un oracolo casuale (il che porterebbe a un argomento circolare sulla conoscenza della chiave), modificano il cifrario ideale in un numero limitato di posizioni in modo coerente con le query classiche già effettuate. Questo permette di "resettare" le modifiche in fasi successive della dimostrazione, mantenendo l'indistinguibilità tra il mondo reale e quello ideale.

3. Contributi Chiave e Risultati

Il lavoro fornisce le prime prove di sicurezza post-quantum rigorose per diverse categorie di costruzioni simmetriche:

A. Costruzione FX (Estensione della Lunghezza della Chiave)

• Analisi: La costruzione FX trasforma un cifrario a blocchi con chiave $m$ in uno con chiave più lunga ($m+2n$) tramite l'aggiunta di chiavi di "whitening".
• Risultato: Gli autori dimostrano la sicurezza post-quantum nel QICM. Il limite superiore per l'advantage di distinzione è:
  $$\text{Adv} \approx (q_C \sqrt{q_Q} + q_Q \sqrt{q_C}) \cdot 2^{-(m+n)/2}$$
  dove $q_C$ sono le query classiche e $q_Q$ le query quantistiche.
• Tightness: Il limite è dimostrato essere stretto (tight). Gli attacchi quantistici noti (come Grover combinato con BHT o l'algoritmo Offline-Simon) raggiungono esattamente questi limiti di complessità di query.
• Applicazioni: La sicurezza di cifrari leggeri come PRINCE e PRIDE, che si basano su varianti della costruzione FX, è stabilita direttamente da questo risultato.

B. Cifrari a Blocchi Modificabili (Tweakable Block Ciphers)

• Analisi: Vengono analizzate le costruzioni LRW e XEX2 (quest'ultima è la base dello standard XTS-AES per la cifratura dei dischi).
• Risultato: Vengono forniti limiti di sicurezza sia nel modello classico che nel QICM.
  • Per LRW, il limite include un termine aggiuntivo legato alle collisioni classiche ($q_C^2 \cdot 2^{-n}$) e termini quantistici legati alla ricerca della chiave.
  • Per XEX2, il limite è derivato combinando la sicurezza di LRW con quella della funzione hash interna.
• Implicazione: Questi risultati confermano che XTS-AES mantiene la sicurezza post-quantum, purché i parametri siano scelti correttamente, ma evidenziano che gli attacchi quantistici possono ridurre la sicurezza effettiva rispetto al caso classico.

C. Modalità di Cifratura a Blocchi (Block Cipher Modes)

• Teorema di "Lifting" (Teorema 7 e 8): Gli autori dimostrano un teorema generale che permette di "sollevare" (lift) le prove di sicurezza classica di una modalità (come CBC, CTR, GCM, CMAC) alla sicurezza post-quantum.
• Meccanismo: La sicurezza post-quantum di una modalità è limitata dalla somma della sicurezza post-quantum del cifrario a blocchi sottostante (come permutazione pseudocasuale forte, SPRP) e della sicurezza informazionale-teorica della modalità stessa quando il cifrario è sostituito da una permutazione casuale ideale.
• Risultato: Questo teorema semplifica enormemente l'analisi, permettendo di derivare limiti di sicurezza per CBC, ECBC, CMAC, GCM e GCM-SST nel modello post-quantum senza dover riscrivere le dimostrazioni da zero.

4. Significato e Impatto

1. Fondamenti Teorici: Il lavoro stabilisce le basi per una teoria rigorosa della sicurezza post-quantum per la crittografia simmetrica, colmando un vuoto significativo rispetto alla crittografia a chiave pubblica.
2. Validazione degli Standard: Fornisce garanzie formali per schemi ampiamente utilizzati (come XTS-AES per i dischi e GCM per le comunicazioni internet), dimostrando che, con parametri adeguati, rimangono sicuri anche contro avversari quantistici.
3. Ottimizzazione dei Parametri: I limiti ottenuti sono "tight" (stretti), il che significa che non sono eccessivamente conservativi. Questo permette ai progettisti di sistemi di evitare di raddoppiare inutilmente le lunghezze delle chiavi (come spesso si fa per precauzione) e di scegliere parametri basati su analisi precise del compromesso tra query classiche e quantistiche.
4. Nuovi Strumenti Tecnici: Il lemma di resampling per i cifrari ideali è un contributo metodologico che può essere riutilizzato per analizzare altre costruzioni simmetriche in futuro, superando le difficoltà legate alla natura delle permutazioni nel contesto quantistico.

In sintesi, questo articolo rappresenta un passo fondamentale verso la comprensione e la certificazione della sicurezza delle infrastrutture crittografiche simmetriche nell'era quantistica, fornendo sia prove formali che strumenti pratici per l'analisi.