Dimostrazioni di sicurezza e riduzioni negli schemi reticolari

Una dimostrazione di sicurezza per uno schema crittografico è un argomento matematico formale che mostra come la violazione dello schema implichi la risoluzione di un problema difficile sottostante. La dimostrazione non garantisce una sicurezza assoluta; mostra che ogni avversario efficiente contro lo schema può essere trasformato in un risolutore efficiente del problema difficile. Se il problema difficile è intrattabile, lo schema è sicuro.

La fondamentale dimostrazione di Regev del 2005 mostra che un algoritmo a tempo polinomiale in grado di risolvere LWE decisionale può essere usato per risolvere GapSVP (Gap Shortest Vector Problem) nel caso peggiore su reticoli n-dimensionali. La riduzione è quantistica: usa una procedura di campionamento quantistico per trasformare un risolutore LWE in un risolutore di problemi sui reticoli. Ciò significa che LWE è difficile almeno quanto i problemi sui reticoli nel caso peggiore in presenza di calcolo quantistico.

La riduzione di Regev non è stretta: i fattori polinomiali nella riduzione fanno sì che il livello di sicurezza garantito dalla dimostrazione sia in qualche misura più debole di quanto suggeriscano i migliori attacchi conosciuti. Per la scelta pratica dei parametri, i crittografi usano la sicurezza concreta fornita dai migliori attacchi conosciuti (tramite lattice estimator), anziché il limite teorico della riduzione, poiché la riduzione è conservativa.

Uno schema di cifratura basato su LWE è dimostrato IND-CPA (indistinguibilità sotto attacco con testo in chiaro scelto) tramite un argomento ibrido. La dimostrazione mostra che un distinguitore IND-CPA implica un distinguitore LWE. Nel primo ibrido, il testo cifrato reale viene sostituito con una stringa casuale uniforme; l'indistinguibilità segue dall'ipotesi LWE. Questo fornisce una dimostrazione di sicurezza chiara per la cifratura di base basata sui reticoli.

La sicurezza IND-CPA non è sufficiente per i meccanismi di incapsulamento delle chiavi usati in TLS: è necessaria la sicurezza IND-CCA2 (sotto attacco con testo cifrato scelto). La trasformazione di Fujisaki-Okamoto (FO) converte qualsiasi schema IND-CPA in un KEM IND-CCA2 nel Random Oracle Model (ROM). ML-KEM applica una variante della trasformazione FO alla cifratura Module-LWE sottostante, fornendo la sicurezza CCA2 richiesta per la distribuzione nel mondo reale.

Il Random Oracle Model (ROM) modella le funzioni hash come funzioni veramente casuali. Molte dimostrazioni di sicurezza, comprese quelle per la trasformazione FO, richiedono il ROM. In pratica, le funzioni hash come SHA-3 non sono veri oracoli casuali, quindi le dimostrazioni nel ROM non garantiscono la sicurezza nel modello standard. Tuttavia, nella comunità crittografica le dimostrazioni nel ROM sono ampiamente accettate come una forte evidenza di sicurezza.

Una dimostrazione nel modello standard non fa idealizzazioni sulle funzioni hash ed è strettamente più forte di una dimostrazione nel ROM. La maggior parte degli schemi pratici basati sui reticoli usa dimostrazioni nel ROM, perché le dimostrazioni CCA2 nel modello standard per i KEM basati sui reticoli sono molto più complesse e producono parametri concreti peggiori. NIST ha accettato le dimostrazioni basate sul ROM per ML-KEM, ritenendole sufficienti per i livelli di sicurezza prefissati.

La dimostrazione di sicurezza di ML-KEM procede in due passaggi. Innanzitutto, si dimostra che la cifratura Module-LWE sottostante è sicura IND-CPA sotto l'ipotesi M-LWE. In secondo luogo, la trasformazione di Fujisaki-Okamoto (nello specifico, le trasformazioni T e U usate in Kyber) porta questa sicurezza a IND-CCA2 nel quantum ROM (QROM), che gestisce gli avversari che interrogano l'oracolo casuale in sovrapposizione.

Il lattice estimator di Albrecht, Player e Scott è lo strumento standard per calcolare la sicurezza concreta degli schemi basati su LWE. Modella il costo dei migliori attacchi conosciuti ai reticoli (BKZ con sieving o enumerazione) e restituisce una stima della sicurezza in bit per determinati parametri (n, q, sigma). Lo strumento viene aggiornato regolarmente quando vengono pubblicati nuovi algoritmi e modelli dei costi dell'hardware.

L'algoritmo Block Korkine-Zolotarev (BKZ) è il migliore algoritmo pratico di riduzione dei reticoli. BKZ con dimensione del blocco beta trova vettori corti con una complessità di circa 2^{0.292*beta} operazioni di gate usando i migliori algoritmi di sieving. Per ML-KEM-768, la sicurezza classica stimata è di circa 180 bit e quella quantistica di circa 164 bit, ben al di sopra dell'obiettivo di 192 bit.

Le dimostrazioni di sicurezza asintotica mostrano che uno schema è sicuro per parametri sufficientemente grandi, ma non specificano che cosa significhi «sufficientemente grandi» nella pratica. L'analisi della sicurezza concreta colma questa lacuna stimando il costo effettivo del miglior attacco per i parametri scelti. La standardizzazione post-quantistica si basa in larga misura sull'analisi della sicurezza concreta, con parametri scelti per resistere agli attacchi dell'hardware quantistico previsto nell'arco di 30 anni.

Le dimostrazioni di sicurezza degli schemi reticolari riducono la sicurezza dello schema alla difficoltà di LWE o SVP. La riduzione di Regev garantisce che LWE sia difficile almeno quanto i problemi sui reticoli nel caso peggiore. La trasformazione di Fujisaki-Okamoto porta la sicurezza da IND-CPA a IND-CCA2 nel ROM. La sicurezza concreta viene valutata con il lattice estimator usando modelli della complessità di BKZ. I divari nella precisione delle riduzioni fanno sì che, nella pratica, i parametri si basino sulle stime del costo degli attacchi anziché soltanto sui limiti delle riduzioni.