💻 computer science

What Can Verifiable Decapsulation Tests Certify? Pass Bounds and Fault-Recognition Limits for FO-Based KEMs

Questo articolo stabilisce limiti teorici e limiti di riconoscimento dei guasti per la verifica di Meccanismi di Incapsulamento delle Chiavi basati su Fujisaki-Okamoto, dimostrando che i test di decapsulamento black-box sono fondamentalmente vincolati da eventi di colpo-lista localizzati e provando che le operazioni al di fuori del cono di supporto attivo non possono essere certificate a causa degli intrinseci compromessi tra correttezza e completezza.

Autori originali: José Luis Delgado Jiménez

Pubblicato 2026-06-04

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: José Luis Delgado Jiménez

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di assumere un fabbro per costruire una cassaforte ad alta sicurezza (un Meccanismo di Incapsulamento delle Chiavi, o KEM). Vuoi essere sicuro che non abbia preso una scorciatoia, come saltare il passaggio in cui ricontrolla il proprio lavoro prima di consegnarti la chiave.

Nel mondo della crittografia post-quantistica, esiste un modo standard per controllare questo lavoro chiamato trasformata di Fujisaki–Okamoto (FO). È come un controllo di "ri-crittografia": il fabbro decripta un messaggio, lo ri-cripta e confronta il risultato con l'originale. Se corrispondono, la chiave è valida. Se il fabbro salta questo controllo, potrebbe comunque consegnarti la chiave giusta per caso, oppure potrebbe dartene una sbagliata.

Questo articolo introduce un nuovo modo, super-rigoroso, per testare questi fabbri utilizzando la Decapsulazione Verificabile. Ecco la ripartizione di ciò che gli autori hanno scoperto, utilizzando analogie semplici.

1. Il trucco del "Testimone Nascosto"

Gli autori propongono una modifica in cui la chiave finale non si basa solo sul messaggio, ma anche su un "testimone" nascosto (un codice segreto generato durante il ricontrollo).

L'analogia: Immagina che il fabbro debba scrivere un codice segreto su un pezzo di carta dopo aver finito il suo lavoro, ma prima di consegnarti la chiave. Questo codice viene poi sigillato all'interno della chiave stessa.
Il test: Tu (il tester) dai al fabbro una scatola chiusa. Lui deve aprirla, fare il suo lavoro, generare quel codice segreto e restituirti la chiave.
L'inghippo: Non dici loro quale debba essere il codice segreto. Lo saprai solo in seguito. Se il fabbro ha saltato il ricontrollo, non conoscerà il codice segreto. Se indovina il codice sbagliato, la chiave che ti darà sarà errata.

2. Il problema della "Scatola Nera"

L'articolo pone una domanda: Possiamo dimostrare che il fabbro ha effettivamente svolto il lavoro solo guardando la chiave che ci ha dato?

Gli autori dicono sì, ma con dei limiti. Hanno scoperto che il test può certificare che il fabbro ha fatto il lavoro solo se il codice segreto era veramente imprevedibile.

Il limite della "Lista di Colpi" (List-Hit): Immagina che il fabbro sia un imbroglione che cerca di indovinare il codice segreto. Se ha una lista di 1も00 possibili codici, ha una possibilità su 100 di indovinarlo per fortuna. L'articolo dimostra che la probabilità che il fabbro superi il test è direttamente legata alla dimensione della sua "lista di tentativi".
La conclusione: Se il fabbro supera il test, è perché ha svolto il lavoro correttamente, oppure perché è stato incredibilmente fortunato con un tentativo di indovinare. Il test non può distinguere tra "lavoro duro" e "tentativo fortunato" a meno che non si possa dimostrare che l'indovinare fosse impossibile.

3. Il "Cono di Dipendenza" (Ciò che non puoi vedere)

Questa è la parte più profonda dell'articolo. Gli autori definiscono un "Cono di Dipendenza".

L'analogia: Pensa al lavoro del fabbro come a un albero. Il "codice segreto" è il frutto all'apice della chioma. Il "Cono di Dipendenza" è l'insieme specifico di rami e foglie che devono essere toccati per far crescere quel frutto.
La scoperta: Se il fabbro salta un passaggio che si trova fuori da questo cono (come lucidare una foglia che non influisce sul frutto), nessun test a scatola nera può dimostrare che lo ha saltato.
Perché? Perché puoi costruire un fabbro "finto" che salta quel passaggio specifico ma produce esattamente lo stesso frutto (chiave) e lo stesso tracciato cartaceo. Per un osservatore esterno, il fabbro falso appare identico a quello reale.
La regola: Puoi certificare che il fabbro ha svolto il lavoro solo se il passaggio saltato era dentro il cono che porta al codice segreto. Se è fuori, il test è cieco a tale omissione.

4. Due modi per superare il test

L'articolo mostra due modi in cui un fabbro può essere provato aver svolto il lavoro:

La via della "Sicurezza della Sorgente": Se il codice segreto è generato in un modo che è matematicamente provato essere indovinabile (come un generatore di numeri casuali perfetto), allora superare il test prova che il lavoro è stato svolto.
La via dell' "Entropia": Se il codice segreto è abbastanza lungo e disordinato (alta entropia), la probabilità di indovinarlo è così piccola che è praticamente nulla. L'articolo calcola esattamente quanto deve essere lungo e disordinato il codice per rendere il test affidabile.

5. Test nel mondo reale (ML-KEM e HQC)

Gli autori hanno testato questa teoria su due standard crittografici reali: ML-KEM (usato in FIPS 203) e HQC.

L'esperimento: Hanno creato versioni "mutanti" del codice che intenzionalmente saltavano dei passaggi (come saltare il ricontrollo o ignorare parte del confronto).
I risultati:
- Errori di Vincolo (Binding Faults): Quando il mutante saltava la parte che genera il codice segreto, il test li beccava il 100% delle volte.
- Errori di Decisione (Decision Faults): Quando il mutante saltava un passaggio che contava solo per input errati (come una scatola malformata), il test non li beccava su input corretti. Questo dimostra che il test è affidabile quanto gli input che gli vengono forniti.
- Errori Simmetrici (Symmetric Faults): Se il mutante saltava il passaggio sia dal lato del mittente che da quello del ricevente, il test non riusciva a beccarli quando testavano se stessi (perché concordavano tra loro). Ma quando testati contro un riferimento "onesto", il test li ha beccati.

6. La trappola dell' "Autotest"

Una scoperta fondamentale è che testare se stessi non è sufficiente.

L'analogia: Se uno studente scrive un esame e poi corregge il proprio compito, potrebbe darsi un voto sufficiente anche se ha barato, perché sa quali dovrebbero essere le risposte.
Il verdetto dell'articolo: Per verificare davvero il lavoro, serve un test di "Riferimento Onesto". Hai bisogno di una parte terza, fidata (l'armatura/harness), per controllare il lavoro rispetto a una verità nascosta. Se il sistema controlla solo se stesso, può nascondere molti tipi di imbroglio.

Sintesi delle affermazioni

Ciò che il test certifica: Certifica che il sistema ha computato un valore specifico di "testimone segreto".
Ciò che il test NON può certificare: Non può certificare che il sistema ha eseguito ogni singolo passaggio dell'algoritmo, ma solo i passaggi che influenzano direttamente quel testimone segreto.
La regola del "Cono": Se un passaggio è fuori dal "cono" di influenza che porta al testimone segreto, un test a scatola nera non può dimostrare che sia stato eseguito.
La regola dell' "Indovinare": Il test è forte quanto la difficoltà di indovinare il testimone segreto. Se il testimone è breve, il sistema può superare il test semplicemente indovinando.

In breve, questo articolo fornisce un libro di regole matematiche su come costruire un "rilevatore di bugie" per il codice crittografico. Ci dice esattamente cosa quel rilevatore di bugie può vedere, a cosa è cieco e come rendere il "codice segreto" così difficile da indovinare da rendere il rilevatore affidabile.

Riepilogo Tecnico: Test di Decapsulazione Verificabile per KEM basati su FO

Problema

I Meccanismi di Incapsulamento Chiave (KEM) post-quantistici basati sulla trasformata di Fujisaki–Okamoto (FO) si affidano a un controllo critico di decapsulazione: l'algoritmo deve decapsulare un ciphertext, riderivare la casualità di cifratura, ricalcolare il ciphertext e confrontarlo con quello ricevuto prima di derivare la chiave condivisa. Sebbene questo controllo sia critico per la sicurezza, i test standard black-box di input-output spesso non riescono a rilevare guasti specifici dell'implementazione. Un'implementazione potrebbe omettere parti del calcolo di ri-cifratura o alterare la logica di selezione dei rami, pur restituendo la chiave condivisa attesa su ciphertext generati onestamente, eludendo efficacemente il controllo di sicurezza senza attivare un fallimento in un normale harness di test.

Il documento affronta la questione di cosa possa essere formalmente certificato riguardo l'esecuzione di questi controlli di decapsulazione utilizzando il testing black-box, specificamente quando il KEM è aumentato con codici di conferma.

Metodologia e Modello

Gli autori propongono una teoria formale della decapsulazione FO aumentata con codice di conferma testata sotto un harness di riferimento onesto.

La Costruzione Aumentata

Il modello estende i KEM standard basati su FO introducendo un testimone di conferma nascosto $W$ nella derivazione della chiave finale.

Incapsulamento: Genera un ciphertext e un valore di conferma interno $W$ . La chiave finale $K$ è derivata come $K = G_K(\langle \text{good}, B, W \rangle)$ , dove $B$ è un prefisso localizzato del transcript e $G_K$ è un oracolo casuale.
Decapsulazione: Ricalcola il ciphertext e il testimone di conferma $W'$ . La chiave finale è derivata solo se $W' = W$ .
Harness di Riferimento Onesto: L'harness di test fornisce l'input di decapsulazione (ciphertext, chiavi) ma trattiene il testimone nascosto $W$ e la chiave finale $K$ . Il Sistema Sotto Test (SUT) deve interrogare l'oracolo casuale $G_K$ con la tupla corretta $\langle \text{good}, B, W \rangle$ per produrre la chiave corretta.

Framework Teorico

Il documento definisce una lista di query della chiave finale localizzata $Q_G(B)$ , che rappresenta l'insieme dei candidati testimoni che il SUT interroga contro l'oracolo casuale. Il nucleo della metodologia consiste nel limitare la probabilità che un SUT difettoso superi il test (ovvero, restituisca la chiave corretta) analizzando la probabilità di un "list hit"—l'evento in cui il testimone nascosto $W$ è presente in $Q_G(B)$ .

L'analisi distingue tra:

Testing di Riferimento Onesto: Confronta il SUT contro un peer onesto e corretto generato dal riferimento.
Testing Self-Honest: Confronta il SUT contro se stesso (sia l'incapsulamento che la decapsulazione provengono dal SUT).
Coni di Dipendenza: Identifica l'insieme delle operazioni che influenzano effettivamente il vettore target osservabile (il transcript e la chiave finale).

Contributi Chiave

1. Teorema del Rilevamento del List-Hit Stretto

Il risultato centrale (Teorema 5.1) stabilisce che per qualsiasi SUT $q$ -localizzato, la probabilità di successo sotto un harness di riferimento onesto è limitata da:
$\text{Pass} \leq \delta_{\Pi_C} + \epsilon_{\text{alias}} + \epsilon_{\text{fresh}} + \Pr[W \in Q_G(B)] + 2^{-\kappa}$
Dove:

$\delta_{\Pi_C}$ è l'errore di correttezza onesta.
$\epsilon_{\text{alias}}$ tiene conto dell'aliasing avversariale (collisioni nella codifica della chiave finale).
$\epsilon_{\text{fresh}}$ tiene conto dei difetti di freschezza della chiave finale (leakage del punto nascosto).
$\Pr[W \in Q_G(B)]$ è il termine di list-hit, che rappresenta la probabilità che il SUT indovini il testimone nascosto.
$2^{-\kappa}$ è il termine di coincidenza dell'oracolo casuale.

Il documento dimostra che questo limite è stretto (Teorema 5.2): qualsiasi predittore di $W$ dalla vista del SUT induce un SUT a singola query con una probabilità di successo che corrisponde al tasso di successo del predittore. Pertanto, il termine di list-hit è l'ostruzione fondamentale misurata dall'harness.

2. Due Percorsi per Limitare il Termine di List-Hit

Il documento fornisce due metodi distinti per limitare il termine inevitabile di list-hit:

Percorso di Sicurezza della Sorgente (cUP-faithful): Se l'harness è "cUP-faithful" (fedele al gioco di imprevedibilità del codice di conferma della sorgente), la probabilità di list-hit è limitata da $q \cdot \epsilon_{\text{cUP}}$ , dove $\epsilon_{\text{cUP}}$ è il vantaggio di un avversario a singolo candidato nel gioco della sorgente. Questo trasferisce le prove di sicurezza della sorgente al contesto di testing con una perdita lineare nel numero di query.
Percorso Entropico: Se il testimone $W$ ha un'entropia minima condizionata media $\lambda$ data la vista del SUT, la probabilità di list-hit è limitata da $q \cdot 2^{-\lambda}$ . Questo percorso accoglie codici diagnostici (ad esempio, hash troncati) dove i limiti cUP della sorgente potrebbero non applicarsi direttamente.

3. Limite Inferiore del Cono di Dipendenza (Risultato Negativo)

Il documento dimostra un limite fondamentale alla certificazione black-box (Teorema 5.37). Se un'operazione si trova al di fuori del cono di dipendenza attivo-supporto del target osservabile (ovvero, cambiare quell'operazione non cambia il transcript osservabile o la chiave finale su supporto onesto), allora nessun test black-box di riferimento onesto può certificarne l'esecuzione su una classe di implementazione contenente la corrispondente "erasure" (una versione del codice che salta l'operazione).

Per tali operazioni, gli errori di correttezza ( $\alpha$ ) e completezza ( $\beta$ ) di qualsiasi certificatore soddisfano $\alpha + \beta \geq 1$ .
Ciò implica che, senza strumentazione aggiuntiva, input malformati o un set di target più ampio, i test black-box non possono distinguere tra l'esecuzione corretta e l'erasure di operazioni al di fuori del cono.

4. Istanze e Artefatto

La teoria è istanziata su due famiglie:

ML-KEM (FIPS 203): Analizza la linea del codice di conferma della sorgente (usando coefficienti non compressi selezionati) e una variante di artefatto diagnostico (ML-KEM-CD1) utilizzando un codice hash di un byte.
HQC (Specifica Agosto 2025): Analizza varianti FO salate dove il codice di conferma è derivato dalla coda troncata del ciphertext. Il documento definisce HQC-TailEnt, un assunto richiesto per limitare il termine di list-hit per questi codici derivati dalla coda.

Gli autori forniscono FO-FaultBench, un artefatto riproducibile contenente:

Baseline fissate (mlkem-native, HQC August 2025).
Varianti trasformate (VSFO/CD1, CD*).
Cataloghi di mutanti (difetti di binding, difetti decisionali, difetti simmetrici).
Record JSONL congelati di esecuzioni sperimentali.

Risultati Sperimentali

Le campagne dell'artefatto validano le affermazioni teoriche:

Difetti di Binding: I difetti che omettono o sovrascrivono il codice di conferma vengono rilevati sotto il testing di riferimento onesto, poiché alterano l'input della chiave finale.
Difetti Solo-Decisionali: I difetti che influenzano solo la selezione dei rami (ad esempio, selezionare sempre la chiave "good") sono non rilevati su ciphertext onesti, ma rilevati sotto harness malformati o differenziali. Ciò conferma il limite di coincidenza del supporto.
Difetti Simmetrici: I difetti applicati sia all'incapsulamento che alla decapsulazione passano i self-test ma falliscono i test di riferimento onesto, dimostrando la necessità del modello peer.
Indovinare Probabilistico: I mutanti che indovinano il codice di conferma passano con una probabilità che scala con la lunghezza del codice mantenuto ( $2^{-L}$ ), corrispondendo ai limiti entropici teorici.
Budget di Range: Gli esperimenti sulle varianti HQC (CD1 vs. CD*) mostrano che aumentare i bit della coda mantenuta (da 5 a 37 bit) riduce significamente la probabilità di successo dei mutanti che indovinano, validando il percorso entropico.

Significato e Dichiarazioni

Il documento dichiara di fornire una teoria formale del testing del codice di conferma che delinea precisamente ciò che i test black-box possono e non possono certificare per i KEM basati su FO.

Affermazioni Positive: Il documento stabilisce che il binding del codice di conferma crea un segnale rilevabile per i difetti di ri-cifratura, a condizione che il termine di list-hit sia limitato dalla cUP della sorgente o dall'entropia condizionata. Offre un framework rigoroso per interpretare i risultati dei test come evidenza per specifiche classi di difetti.
Affermazioni Negative: Il documento dichiara esplicitamente che il testing black-box di riferimento onesto ha limiti intrinseci. Non può certificare operazioni al di fuori del cono di dipendenza (ad esempio, l'esecuzione completa della ri-cifratura se solo un sottoinsieme di coefficienti è vincolato) senza cambiare il target dell'harness o aggiungere strumentazione.
Modestia: Gli autori sottolineano che i teoremi di testing sono affermazioni classiche del Modello di Oracolo Casuale (ROM). Non riprovano la sicurezza IND-CCA dei KEM sottostanti, ma si affidano alle analisi di sicurezza della sorgente citate per la costruzione. La "sicurezza" delle linee aumentate è ereditata dalla sorgente; il contributo del documento è il segnale di testing e l'interpretazione delle probabilità di successo sotto configurazioni specifiche dell'harness.

Il lavoro funge da ponte tra i giochi di sicurezza teorici (cUP, fCOR) e il testing pratico delle implementazioni KEM post-quantistiche, fornendo una "grammatica di rivendicazione" per interpretare i risultati sperimentali.