Sintesi Tecnica: L'Aritmetica Centrata Non è Neutrale rispetto alla Leakage

Problematica

Nelle implementazioni software della crittografia basata su reticoli (es. ML-KEM, ML-DSA), i valori sensibili sono protetti tramite masking aritmetico, in cui un segreto viene suddiviso in share casuali la cui somma è il segreto modulo $q$. Sebbene l'operazione matematica sia modulare, lo stoccaggio fisico di queste share richiede una scelta di rappresentazione all'interno della parola macchina. Tipicamente, le share sono memorizzate o come residui non con segno nell'intervallo $[0, q)$ o come interi con segno centrati in complemento a due nell'intervallo $[-\lfloor q/2 \rfloor, \lceil q/2 \rceil - 1]$.

Sebbene entrambi i codici implementino l'aritmetica modulare in modo identico, essi differiscono significativamente nella rappresentazione binaria. Nello specifico, gli interi negativi in complemento a due esibiscono estensione del segno (leading ones), mentre i loro corrispettivi non con segno no. Lavori precedenti hanno sfruttato questo effetto di "estensione del segno" per attacchi side-channel (es. predittori del valore assoluto). Tuttavia, mancava un quadro teorico completo che caratterizzasse come questa scelta di rappresentazione influenzi la leakage attraverso tutti gli ordini di masking, sotto rumore finito e per moduli arbitrari. Questo articolo affronta la domanda fondamentale: L'aritmetica centrata è neutrale rispetto alla leakage rispetto allo stoccaggio non con segno?

Metodologia

L'articolo impiega un approccio matematico rigoroso combinando la teoria della probabilità, l'analisi di Fourier e la teoria dei numeri combinatoria per modellare il canale di leakage side-channel.

1. Modellazione del Canale a Rumore Finito: L'autore modella la leakage delle share mascherate come canali di rumore additivo indipendenti. Deriva la verosimiglianza esatta della somma mascherata trattando il problema come una convoluzione ciclica delle distribuzioni di leakage delle singole share.
2. Analisi di Fourier: L'analisi utilizza la Trasformata Discreta di Fourier (DFT) per convertire la convoluzione in un prodotto nel dominio della frequenza. Ciò consente la derivazione di attacchi ottimali e la decomposizione spettrale della leakage.
3. Minimax della Rappresentazione: Lo studio valuta diverse "sezioni" (rappresentazioni) di $\mathbb{Z}_q$ minimizzando l'energia dello spettro di leakage. Ciò comporta il confronto tra sezioni contigue (non con segno vs centrata) e arbitrari codebook binari iniettivi.
4. Decomposizione Spettrale: Una chiave innovazione metodologica è la decomposizione dello spettro di leakage del complemento a due centrato in termini di estensione del segno e termini di carry (riporto), permettendo un'analisi asintotica precisa.
5. Validazione Algoritmica: I limiti teorici sono verificati attraverso computazioni esatte, esperimenti sintetici con parametri completi di ML-KEM e ML-DSA, e l'analisi di tracce fisiche pubbliche.

Contributi Chiave

1. Inferenza Ottimale a Rumore Finito

L'articolo stabilisce che la verosimiglianza completa di una somma mascherata può essere calcolata in tempo quasi-lineare $O(dq \log q)$ utilizzando una convolvoluzione circolare valutata tramite Fast Fourier Transform (FFT).

• Risultato: Questo fornisce una strategia di attacco ottimale che valuta tutte le $q$ ipotesi simultaneamente.
• Condizione di Sufficienza: L'autore deriva una condizione esatta sotto la quale la comunemente utilizzata statistica del prodotto (moltiplicazione di share centrate) conserva tutta l'informazione di verosimiglianza. Dimostra che per tabelle di leakage non negative con uno zero unico, la statistica del prodotto è strettamente insufficiente per qualsiasi modulo $q \ge 2$ e ordine $d \ge 2$ sotto rumore finito. L'osservazione completa contiene strettamente più informazione (maggiore divergenza KL, divergenza di Rényi, ecc.) rispetto alla statistica del prodotto.

2. Leggi Minimax della Rappresentazione Globale

L'articolo ottimizza la scelta della rappresentazione per minimizzare la leakage:

• Leakage del Primo Ordine: Tra tutte le sezioni contigue, lo stoccaggio non con segno ($[0, q)$) è l'unico minimizzatore della leakage del primo ordine, a meno che il modulo $q$ non occupi l'intera parola macchina ($q=2^m$), nel quale caso tutte le sezioni sono equivalenti.
• Leakage di Ordine Superiore: L'ottimalità dello stoccaggio non con segno non è permanente. L'articolo identifica un esatto "cambio di fase" dove, per parametri specifici (es. $q=14, \beta=4$), lo stoccaggio centrato diventa l'unico minimizzatore per ordini $d \ge 4$, mentre quello non con segno è ottimale per ordini inferiori.
• Legge Lessicografica: Per qualsiasi famiglia finita di rappresentazioni, l'eventuale minimizzatore all'aumentare dell'ordine di masking $d \to \infty$ è determinato dallo spettro delle coefficienti di leakage ordinato lessicograficamente più piccolo.
• Codebook a Peso Costante: Per codifiche binarie arbitrarie, la leakage svanisce esattamente se e solo se il codebook ha un peso di Hamming costante. L'articolo fornisce un limite di capacità netto per l'esistenza di tali codebook ($q \le \binom{\beta}{\lfloor \beta/2 \rfloor}$) e calcola la larghezza minima della parola richiesta per gli standard NIST (es. $\beta=14$ per $q=3329$).

3. La Legge della Riduzione Centrata

Il risultato teorico centrale dell'articolo è una decomposizione spettrale esatta della leakage del complemento a due centrato:

• Decomposizione: Lo spettro di leakage è diviso in un termine macroscopico di estensione del segno e un difetto di carry binario.
• Soglia di Dominanza: L'articolo dimostra una soglia uniforme netta: sono necessari tre bit in eccesso ($s = \beta - \lceil \log_2 q \rceil \ge 3$) affinché lo stoccaggio centrato presenti una magnitudo di leakage strettamente maggiore rispetto allo stoccaggio non con segno al primo modo di Fourier. Nello specifico, la condizione $D(q, \beta) > 2U(q)$ vale se e solo se $s \ge 3$.
• Asintotica: Per larghezza in eccesso fissa, il rapporto tra i coefficienti di leakage centrata e non con segno converge a $s+1$. Per il caso specifico di $q=2^m-1$, il rapporto di leakage converge a una costante correlata alla somma delle tangenti ($\kappa \approx 1.81$).
• Neutralità: L'aritmetica centrata non è neutrale rispetto alla leakage. È neutrale (equivalente alla leakage non con segno) solo nel caso esatto in cui $q=2^m$ e $\beta=m$. In tutti gli altri casi, lo stoccaggio centrato risulta in una leakage strettamente maggiore al primo modo di Fourier (e tipicamente per bassi ordini di masking), sebbene possa diventare la rappresentazione ottimale ad ordini molto elevati per specifici set di parametri.

4. Robustezza e Complessità Campionaria

• Raggi di Robustezza: L'articolo definisce esatti raggi di robustezza per modelli a peso di Hamming pesato, mostrando che la separazione netta tra stoccaggio centrato e non con segno persiste anche con variazioni di sensibilità del bit, purché la larghezza in eccesso sia almeno 3.
• Complessità Campionaria: Viene proposto un test armonico a confidenza esponenziale. L'articolo dimostra che il rapporto di complessità campionaria tra attacchi centrati e non con segno scala come la $2d$-esima potenza del rapporto tra i loro coefficienti spettrali. Ciò implica che per ordini di masking più elevati, la penalità per l'uso dello stoccaggio centrato (che ha una maggiore leakage al primo modo) cresce esponenzialmente, a meno che il set di parametri specifico non collochi il sistema in un regime in cui lo stoccaggio centrato è il minimizzatore globale.

Risultati e Validazione

• Esperimenti Sintetici: Implementazioni complete per ML-KEM ($q=3329$) e ML-DSA ($q=8380417$) confermano i fattori di complessità campionaria teorici. Per $d=3, 4, 6$, la rappresentazione centrata richiede significativamente più tracce rispetto alla rappresentazione non con segno per raggiungere lo stesso tasso di successo, allineandosi ai limiti asintotici derivati.
• Tracce Fisiche: L'analisi è stata validata contro tracce fisiche pubbliche da un'implementazione mascherata di ML-DSA. Il predicato del segno ha raggiunto un Welch $|t|$ di 155.73 e un'accuratezza bilanciata del 90.80%, confermando la presenza del canale di leakage dell'estensione del segno predetto dalla teoria.
• Efficienza Algoritmica: L'attacco ottimale proposto (utilizzando la convoluzione basata su FFT) ha completato con successo il punteggio di tutte le ipotesi per $q=8,380,417$ in meno di 35 secondi, dimostrando la fattibilità pratica.

Significato

L'articolo sposta fondamentalmente la comprensione del masking aritmetico nel software. Dimostra che la scelta della rappresentazione della macchina (centrata vs non con segno) non è un semplice dettaglio di implementazione, ma una componente critica del canale di leakage side-channel.

• Confutazione della Neutralità: L'autore dimostra conclusivamente che "L'Aritmetica Centrata Non è Neutrale rispetto alla Leakage". L'estensione del segno inerente alla rappresentazione in complemento a due introduce uno spettro di leakage distinto che non viene mitigato dal solo masking.
• Linee Guida di Design: Il lavoro fornisce linee guida azionabili ed esatte per gli implementatori:
  • Utilizzare lo stoccaggio non con segno per la sicurezza del primo ordine e quando i bit in eccesso sono bassi ($s < 3$), poiché minimizza unicamente la leakage del primo ordine.
  • Essere consapevoli che lo stoccaggio centrato generalmente incorre in una severa penalità nella complessità campionaria a causa della maggiore leakage al primo modo, diventando ottimale solo ad ordini molto elevati per specifici set di parametri (dimostrando un cambio di fase nell'ottimalità).
  • I codebook a peso costante offrono una via teorica verso la leakage zero, ma richiedono larghezze di parola specifiche che potrebbero non allinearsi con i vincoli hardware standard.
• Fondamento Teorico: Fornendo leggi spettrali esatte e condizioni di ottimalità a rumore finito, l'articolo colma il divario tra la sicurezza del masking teorico e le realtà pratiche dell'implementazione, offrendo una base rigorosa per valutare e progettare sistemi crittografici basati su reticoli resistenti ai side-channel.