Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768 at the Heuristic Failure Scale

Nel mondo digitale, la sicurezza si affida spesso a problemi matematici che sono facili da usare in una direzione, ma estremamente difficili da invertire senza le giuste informazioni segrete. ML-KEM è un meccanismo di stabilimento delle chiavi post-quantistiche progettato per rimanere sicuro anche contro i futuri computer quantistici. Come altri sistemi crittografici basati su reticoli, presenta una probabilità estremamente piccola di quella che viene chiamata un'onesta mancata decapsulazione: anche quando entrambe le parti si comportano correttamente, i due lati potrebbero in linea di principio derivare chiavi diverse. Stimare quanto raramente ciò possa accadere è una questione importante di correttezza. Le analisi precedenti si sono ampiamente basate su stime euristiche della scala di fallimento, mentre l'ottenimento di un limite rigoroso che preservi le rilevanti dipendenze matematiche tra i diversi termini di errore è sostanzialmente più difficile.

Uno studio recente di Aurélie Duriez e Christophe Tommasini affronta questo problema sviluppando un'analisi matematica rigorosa di ML-KEM-768 all'interno di un'esplicita astrazione idealizzata di funzione casuale / binomiale centrata, o ROM/CBD. Il lavoro non è una simulazione e non tenta di calcolare il tasso di fallimento esatto. Invece, gli autori derivano un limite superiore certificato sulla probabilità di un'onesta mancata decapsulazione preservando le importanti dipendenze tra i diversi termini di errore. In particolare, l'analisi tiene traccia delle dipendenze indotte dalla matrice pubblica e da entrambi i termini di compressione del testo cifrato, invece di trattarli semplicemente come indipendenti. Il limite superiore certificato risultante è inferiore a uno su 2 alla potenza di 164,81.

Questo risultato è significativo perché sostituisce una stima euristica della scala di fallimento, all'interno del modello esplicito studiato, con un limite superiore certificato che tiene conto delle dipendenze. L'analisi non assume semplicemente che gli errori rilevanti siano indipendenti; essa preserva le dipendenze matematiche che derivano tra di essi. Il limite certificato raggiunge essenzialmente la stessa scala delle precedenti stime euristiche, ma ciò non deve essere interpretato come la prova che tali stime siano l'esatta probabilità di fallimento. Il risultato è deliberatamente più ristretto: all'interno dell'astrazione ROM/CBD esplicita studiata nel documento, la probabilità di un'onesta mancata decapsulazione è rigorosamente limitata superiormente da un valore estremamente piccolo. Il documento chiarisce inoltre che questo non è un tasso di mancata decapsulazione esatto e non è un'affermazione informazionale-teorica sull'istanza SHAKE fissa di FIPS 203.

Il lavoro ha richiesto un approccio diverso al problema. Le analisi euristiche semplificate possono diventare molto più facili se alcuni termini di errore vengono trattati come indipendenti, ma la reale struttura algebrica crea dipendenze che un'analisi rigorosa deve preservare. Gli autori hanno quindi sviluppato un metodo che segue queste dipendenze attraverso il calcolo invece di scartarle. Il processo di ricerca ha inoltre utilizzato una metodologia assistita dall'IA per esplorare approcci candidati, identificare casi critici e strutturare l'analisi. Questo uso esplorativo dell'IA è stato combinato con controlli esaustivi verificati dal computer, aritmetica esatta o certificata e computazioni verificabili indipendentemente per chiudere le parti più difficili dell'argomentazione. Le rivendicazioni matematiche finali si basano quindi su prove esplicite e riproducibili piuttosto che sull'output dell'IA stessa.

Il risultato è un limite di correttezza certificato, rigoroso e trasparente, all'interno dell'astrazione dichiarata. I ricercatori hanno reso disponibili il loro codice, i dati e gli artefatti di supporto in modo che le computazioni possano essere controllate indipendentemente. Questo livello di riproducibilità è particolarmente importante nella crittografia, dove le affermazioni matematiche dovrebbero essere aperte alla verifica indipendente. Lo studio mostra che, all'interno dell'astrazione ROM/CBD considerata, la probabilità di un'onesta mancata decapsulazione è limitata a un livello estremamente piccolo. Non deve tuttavia essere interpretato come un certificato generale di sicurezza per ML-KEM-768, come una prova di tutte le proprietà di sicurezza dello schema standardizzato, o come un'affermazione che copra ogni implementazione hardware o software.

Questo risultato fa progredire la comprensione rigorosa di un aspetto specifico della correttezza di ML-KEM-768, passando da una stima euristica della scala di fallimento a un limite superiore certificato che tiene conto delle dipendenze all'interno di un'astrazione chiaramente definita. Dimostra che è possibile stabilire un limite alla scala euristica pur preservando le importanti dipendenze tra i termini di errore rilevanti. Il numero 164,81 è l'esponente certificato di questo limite superiore: all'interno della dichiarata astrazione ROM/CBD, la probabilità di mancata decapsulazione onesta è limitata superiormente a 2 alla potenza di -164,81. Questo numero deve quindi essere inteso come una proprietà precisa del limite certificato provato nel documento, piuttosto che come una misura generale della sicurezza o della protezione di ML-KEM-768 nel suo complesso.

I ricercatori hanno inoltre avuto cura di spiegare i limiti del loro lavoro. Hanno sottolineato che la loro prova si applica a un'astrazione specifica del sistema, non necessariamente a ogni possibile implementazione del software. Non hanno sostenuto di aver risolto il problema per tutte le variazioni dello standard di crittografia, né hanno suggerito che il sistema sia immune a tutti i tipi di attacchi. Il loro focus era strettamente limitato alla correttezza del processo di decifrazione in condizioni oneste. Essendo stati chiari su ciò che hanno provato e su ciò che non hanno provato, si sono assicurati che le loro scoperte non venissero interpretate erroneamente. Lo studio è una testimonianza della potenza di un'analisi attenta e dettagliata in un campo in cui piccoli errori possono avere enormi conseguenze. Dimostra che con abbastanza rigore e gli strumenti giusti, anche i sistemi matematici più complessi possono essere compresi e verificati.

In definitiva, il documento fornisce un risultato preciso ma deliberatamente limitato: all'interno della dichiarata astrazione ROM/CBD, la probabilità di mancata decapsulazione onesta è rigorosamente limitata superiormente a 2 alla potenza di -164,81. Si tratta di un limite superiore certificato estremamente piccolo, ma non è un tasso di fallimento esatto e non è una prova globale che il sistema ML-KEM-768 completamente distribuito funzioni senza errori in ogni condizione del mondo reale. Il contributo risiede nel sostituire una stima euristica della scala di fallimento con un limite riproducibile, verificabile indipendentemente e che tiene conto delle dipendenze all'interno di un modello chiaramente definito. La sua forza non deriva dal rivendicare una certezza oltre quel modello, ma dall'essere esplicito sia su ciò che è stato provato sia su ciò che rimane al di fuori dell'ambito del risultato.