💻 computer science

Fresh Masking Makes NTT Pipelines Composable: Machine-Checked Proofs for Arithmetic Masking in PQC Hardware

Questo lavoro presenta nove teoremi verificati meccanicamente in Lean 4 che dimostrano come l'applicazione di maschere fresche a ogni stadio delle pipeline NTT garantisca la sicurezza contro il probing di primo ordine per gli acceleratori crittografici PQC, fornendo inoltre una spiegazione formale delle vulnerabilità strutturali dell'acceleratore Adams Bridge.

Autori originali: Ray Iskander, Khaled Kirah

Pubblicato 2026-04-23

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Ray Iskander, Khaled Kirah

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

🛡️ Il Segreto dei "Falsi Indizi" e la Catena di Sicurezza

Immagina di dover proteggere un segreto prezioso (come la chiave per una cassaforte digitale) mentre lo trasporti attraverso una serie di stanze (i passaggi di un computer). Per farlo, usi un trucco antico: dividi il segreto in due metà e le dai a due persone diverse. Nessuno delle due metà da sole ti dice nulla. Questo si chiama "mascheramento".

Il problema è: cosa succede se queste due metà devono attraversare una lunga catena di stanze (un "pipeline" di elaborazione)? Se ogni stanza è sicura da sola, l'intera catena è sicura?

Gli ingegneri pensavano di sì, ma si sbagliavano. Questo articolo scientifico, scritto da Ray Iskander e Khaled Kirah, usa un "super-matematico" (un software chiamato Lean 4) per dimostrare esattamente come funziona la sicurezza in queste catene e, soprattutto, perché un famoso progetto chiamato "Adams Bridge" non è sicuro come pensavamo.

Ecco i tre concetti chiave, spiegati con metafore:

1. La Trappola dell'"Indizio Falso" (Il Trucco del Magico)

Immagina di essere un detective che controlla se una stanza è sicura. Il tuo primo pensiero è: "Se cambio il segreto che porto dentro, il valore che vedo sulla scrivania cambia?"
Se la risposta è "Sì, cambia", pensi: "Oh no! La stanza è insicura! Il segreto sta trapelando!".

Il paper dice: "Fermati! È una trappola!" 🚫

Nel mondo della crittografia moderna (quella che resisterà ai computer quantistici), c'è un trucco matematico chiamato Butterfly (farfalla). È come un incrocio stradale dove le informazioni si mescolano.

La trappola: Se guardi un singolo cavo (un "filo") e cambi il segreto, il valore sul filo cambia davvero, anche se hai usato il trucco della divisione. Un detective frettoloso direbbe: "È insicuro!".
La realtà: Anche se il valore cambia, la distribuzione (la probabilità di trovare quel valore) rimane perfettamente casuale e uguale per tutti i segreti. È come se cambiassi il colore della tua maglietta, ma la probabilità che un estraneo indovini il tuo nome rimanesse 1 su un milione.

La lezione: Non fidarti del primo indizio visivo. Devi guardare la "statistica" (la distribuzione), non il singolo valore. Gli autori hanno scritto un "avviso" ufficiale per gli ingegneri: "Non controllare se il valore cambia, controlla se la distribuzione è uniforme!".

2. La Catena di Sicurezza: Il Principio della "Maschera Fresca" 🎭

Ora immagina la catena di stanze (il "pipeline").

Scenario A (Sicuro): Ogni volta che passi da una stanza all'altra, ricevi una nuova maschera fresca (un nuovo numero casuale) che ti copre completamente. È come se ogni stanza ti desse un nuovo mantello invisibile.
Scenario B (Insicuro - Adams Bridge): La prima stanza ti dà un mantello, ma nelle stanze successive ti togli il mantello e cammini nudo, pensando che il primo mantello ti abbia protetto per sempre.

La scoperta del paper:
Gli autori hanno dimostrato matematicamente (con zero errori, usando il software Lean 4) che:

Se usi una nuova maschera fresca in ogni stanza, l'intera catena è sicura. È come avere un nuovo scudo per ogni colpo.
Se non usi una maschera fresca tra le stanze (come fa il progetto Adams Bridge), la sicurezza crolla. Le informazioni si accumulano e il nemico può ricostruire il segreto.

È come se dovessi attraversare un ponte sospeso. Se ogni sezione del ponte ha una nuova corda di sicurezza (maschera fresca), sei al sicuro. Se le corde si interrompono e non ne metti di nuove, il ponte crolla.

3. Il "Super-Matematico" e la Prova Definitiva 🧠💻

Perché questo articolo è speciale?
Fino ad oggi, queste prove erano fatte "a mano" su carta o con simulazioni che potevano avere errori.
Gli autori hanno usato Lean 4, un assistente di prova matematica. È come avere un giudice infallibile che controlla ogni singola riga della tua logica.

Hanno scritto il codice della sicurezza.
Il computer ha controllato ogni possibile scenario (per ogni numero, per ogni tipo di segreto).
Il risultato? Zero errori. La prova è matematicamente perfetta.

Hanno anche dimostrato che il progetto Adams Bridge (usato in alcuni chip reali) viola questa regola: non mette maschere fresche tra le stanze. Ecco perché, come hanno scoperto in lavori precedenti, è vulnerabile agli attacchi.

In Sintesi: Cosa ci dicono questi ricercatori?

Smetti di fidarti dell'intuito: Controllare se un valore cambia non basta. Devi controllare la statistica (la "distribuzione marginale").
La regola d'oro: Per rendere sicura una catena di calcoli crittografici, devi rinfrescare le maschere (aggiungere nuovi numeri casuali) ad ogni passaggio. Senza questo, la sicurezza è un'illusione.
La prova è solida: Non è solo teoria. È una prova verificata da un computer, pronta per essere usata dai certificatori governativi (come quelli che approvano i chip per la sicurezza nazionale).

L'analogia finale:
Immagina di inviare un messaggio segreto in una serie di scatole.

Metodo vecchio (Adams Bridge): Metti il messaggio in una scatola con un lucchetto, poi lo passi a un'altra scatola senza cambiare il lucchetto e senza mettere un nuovo strato di protezione. Chiunque può seguire il filo.
Metodo nuovo (Il paper): Ogni volta che passi la scatola, la rompi, metti il messaggio in una nuova scatola con un nuovo lucchetto e un nuovo codice segreto. Anche se qualcuno ruba una scatola, non può mai ricostruire il messaggio originale perché ogni passaggio è un nuovo inizio.

Questo paper ci dice esattamente come costruire quelle "nuove scatole" in modo matematicamente provato, salvando la nostra crittografia dai computer quantistici del futuro.

1. Il Problema

Il lavoro affronta una lacuna critica nella sicurezza delle accelerazioni hardware per la crittografia post-quantistica (PQC), in particolare per gli standard ML-KEM (FIPS 203) e ML-DSA (FIPS 204).

Contesto: Questi acceleratori utilizzano la Trasformata Numerica Teorica (NTT) implementata come una pipeline di stadi "butterfly" (farfalla) di Cooley-Tukey su anelli $\mathbb{Z}_q$ .
La sfida: Sebbene esistano framework teorici per la composizione sicura di circuiti mascherati (come ISW, t-SNI, PINI, DOM), le loro formalizzazioni machine-checked (verificate da computer) sono limitate al dominio booleano ($GF(2)$). Non esiste alcuna prova formale che garantisca la sicurezza composizionale per il dominio aritmetico specifico dell'NTT su $\mathbb{Z}_q$ .
Il rischio: Gli ingegneri hardware potrebbero erroneamente assumere che se ogni singolo stadio è sicuro, l'intera pipeline lo sia. Tuttavia, la proprietà di sicurezza intuitiva ("indipendenza puntuale del valore") è falsa per le uscite delle farfalle aritmetiche, portando a falsi allarmi o, peggio, a design insicuri.
Caso reale: L'acceleratore Adams Bridge (implementato in CHIPS Alliance Caliptra) presenta vulnerabilità strutturali perché non applica un mascheramento "fresco" (nuovo) tra gli stadi della pipeline, violando implicitamente le ipotesi necessarie per la sicurezza composizionale.

2. Metodologia

Gli autori hanno utilizzato l'assistente di prova Lean 4 con la libreria Mathlib per fornire prove matematiche formali e verificabili ("machine-checked") con zero "sorry" (nessuna assunzione non verificata).

Modellazione: La pipeline NTT è modellata come una sequenza di stadi farfalla, ciascuno protetto da mascheramento aritmetico del primo ordine con un nuovo valore casuale (fresh randomness) per ogni stadio.
Modello di Attacco: Si utilizza il modello di probing di ISW (Ishai-Sahai-Wagner) del primo ordine, dove un avversario può osservare un singolo filo per ciclo di clock.
Approccio: Invece di tentare di adattare i complessi teoremi di composizione non lineari (usati per le porte AND booleane), gli autori sfruttano la struttura affine (lineare) della farfalla NTT rispetto alla maschera. Questo permette una dimostrazione diretta e universale.

3. Contributi Chiave

Il paper presenta tre risultati principali, tutti formalizzati in Lean 4:

Il "Ponte r-bearing" (r-bearing bridge):
- Risolve una limitazione dichiarata nel lavoro precedente degli autori. Dimostra che l'"indipendenza del valore" (value-independence) implica una distribuzione marginale costante sotto l'uso di nuove casualità (fresh randomness).
- Formalizza questo legame tramite un proxy algebrico chiamato MutualInfoZero, chiudendo il divario tra le prove algebriche e la sicurezza informazionale.
Uniformità per Contesto della Farfalla (Butterfly Per-Context Uniformity):
- Smentita di un'ipotesi errata: Dimostra formalmente che la proprietà di "indipendenza puntuale del valore" (il valore del filo non cambia se il segreto cambia mantenendo le maschere fisse) è falsa per le uscite della farfalla. Questo è un "avvertimento" cruciale per i progettisti hardware che potrebbero usare solver SMT e scartare erroneamente design corretti.
- Proprietà corretta: Introduce e prova la uniformità marginale. Per ogni filo di uscita, esiste esattamente un valore di maschera che produce un dato valore di uscita, indipendentemente dai segreti. Questo garantisce che la distribuzione marginale sia uniforme su $\mathbb{Z}_q$ .
- Universalità: La prova vale per qualsiasi modulo $q > 0$ (non solo primi), qualsiasi fattore di rotazione (twiddle factor) e qualsiasi input.
Composizione della Pipeline (Pipeline Composition):
- Dimostra che una pipeline NTT a $k$ stadi, con mascheramento fresco e indipendente per ogni stadio, soddisfa l'uniformità per contesto in ogni stadio.
- Questo è l'invariante algebrico fondamentale per la sicurezza sotto il modello di probing di ISW. La sicurezza dell'intera pipeline deriva dalla somma delle uniformità locali di ogni stadio.

4. Risultati e Artefatti

Prove Formali: Il lavoro include 9 teoremi principali, compilati in 1.738 job di build con zero errori e zero avvisi.
Codice: L'artefatto è composto da circa 580 righe di codice Lean 4, distribuito in tre file.
Analisi di Adams Bridge: Il paper conferma la causa architetturale dell'insicurezza dell'acceleratore Adams Bridge: la violazione del principio di "Fresh Masking" (il mascheramento è attivo solo nel primo stadio, non tra gli stadi successivi). Senza nuove maschere fresche tra gli stadi, il teorema di composizione non si applica e la sicurezza non è garantita.
Validità Universale: Le prove sono valide per tutti i moduli utilizzati negli standard PQC attuali (es. $q=3329$ per ML-KEM, $q=8380417$ per ML-DSA) e per moduli composti futuri.

5. Significato e Implicazioni

Per i Progettisti Hardware: Fornisce una guida chiara su cosa verificare. Sconsiglia di cercare l'indipendenza puntuale (che fallisce) e incoraggia a garantire l'iniezione di maschere fresche e indipendenti tra ogni stadio della pipeline.
Per la Certificazione (FIPS 140-3): Offre un'evidenza matematica verificabile da macchine che può essere citata direttamente nella documentazione di certificazione. Dimostra che un design che segue il "Principio di Mascheramento Fresco" è intrinsecamente sicuro per il probing del primo ordine.
Limiti e Futuro: Il lavoro si concentra sul caso lineare (affine). I casi non lineari (come la riduzione di Barrett o le moltiplicazioni mascherate) richiedono approcci diversi (discussi in un lavoro correlato [3] che introduce il framework PF-PINI). Tuttavia, questo paper risolve il problema fondamentale della composizione delle pipeline NTT, che costituisce la spina dorsale degli acceleratori PQC.

In sintesi, il paper colma un vuoto critico nella verifica formale della crittografia post-quantistica hardware, trasformando un'intuizione di sicurezza in una prova matematica rigorosa e universalmente applicabile, spiegando al contempo perché implementazioni esistenti come Adams Bridge falliscono.