Predicting Module-Lattice Reduction

Sintesi Tecnica: Predire la Riduzione di Moduli di Reticoli

Enunciato del Problema
Il documento affronta una questione critica nella crittanalisi degli schemi crittografici basati su moduli di reticoli (come gli standard NIST ML-KEM, ML-DSA e FN-DSA): la riduzione di moduli di reticoli (specificamente module-BKZ) è più o meno efficiente della riduzione di reticoli non strutturati (BKZ) se dotata dello stesso oracolo SVP (Shortest Vector Problem)?

Mentre i lavori teorici fondamentali hanno stabilito l'esistenza di varianti modulari di LLL e degli algoritmi di riduzione a blocchi, essi si sono concentrati sul comportamento asintotico nel caso peggiore. Una preoccupazione specifica, evidenziata come "Q8" nella sottomissione NIST di Kyber, ipotizza che la struttura algebrica dei moduli di reticoli su campi ciclotomici possa permettere accelerazioni (ad esempio, un fattore da $d$ a $d^2$) o, viceversa, potrebbe degradare la qualità della base ridotta rispetto a BKZ non strutturato. Il documento mira a fornire un'analisi concreta, basata sul caso medio, per rispondere se module-BKZ offra un guadagno o una perdita in termini della dimensione del blocco $\beta$ necessaria per raggiungere una determinata qualità della base (pendenza o slope).

Metodologia
Gli autori impiegano un'analisi euristica supportata da estesi esperimenti per predire la "pendenza" del profilo della base dopo l'esecuzione di module-BKZ. La pendenza è definita come il tasso di decadimento delle norme logaritmiche dei vettori ortogonalizzati di Gram-Schmidt.

1. Implementazione Sperimentale: Gli autori hanno sviluppato la prima implementazione open-source di module-BKZ per campi ciclotomici (fino al conduttore 16), utilizzando le librerie esistenti fplll e G6K. Hanno affrontato sfide tecniche riguardanti la preservazione della struttura del modulo durante la riduzione delle dimensioni (size reduction) e l'uso di un "embedding ciclico" per garantire che il prodotto interno della traccia sia compatibile con le librerie standard di riduzione di reticoli interi.
2. Modellazione Teorica (GSA per Moduli di Reticoli): Estendono la Geometric Series Assumption (GSA), comunemente usata per BKZ non strutturato, ai moduli di reticoli. Ciò comporta la modellazione del profilo $K$ atteso (mediato sul grado $d$ del campo numerico) di una base ridotta.
3. Decomposizione della Pendenza: La pendenza predetta di module-BKZ è scomposta in quattro termini distinti ($t_1$ a $t_4$) che guidano la deviazione da BKZ non strutturato:
   • $t_1$ (Euristica Gaussiana): La lunghezza attesa del vettore più corto in un modulo di reticolo casuale, regolata per il numero di radici dell'unità ($\mu_K$).
   • $t_2$ (Gap del Discriminante): Un termine dipendente dal discriminante $\Delta_K$ del campo $K$.
   • $t_3$ (Gap di Skewness): Misura la deviazione della norma algebrica del vettore dalla sua norma euclidea (skewness del vettore attraverso gli embedding).
   • $t_4$ (Gap di Indice): Tiene conto dell'indice dell'ideale generato dal vettore più corto all'interno del modulo.
4. Analisi Asintotica: Gli autori derivano una formula asintotica per la "dimensione del blocco equivalente" $\beta_{eq}$ richiesta affinché module-BKZ corrisponda alla pendenza di BKZ non strutturato con dimensione del blocco $\beta$.

Contributi Chiave e Risultati

• Predizione Quantitativa della Pendenza: Il documento fornisce una formula concreta che predice la pendenza di module-BKZ in funzione della dimensione del blocco $\beta$, del grado del campo $d$ e del discriminante del campo $\Delta_K$.
• Il Discriminante come Driver: L'analisi identifica il discriminante $\Delta_K$ come la quantità primaria che guida la differenza di prestazione. Nello specifico, il termine $\ln(|\Delta_K|/d^d)$ determina se module-BKZ ottiene un guadagno o una perdita di efficienza.
• Guadagno/Perdita Asintotica della Dimensione del Blocco: Gli autori derivano la seguente relazione asintotica per la dimensione del blocco equivalente $\beta_{eq}$:
  $$\beta_{eq} \approx \beta + \ln\left(\frac{|\Delta_K|}{d^d}\right) \frac{\beta}{d \ln \beta} + (d - 1)$$
  • Campi Ciclotomici Potenza di Due: Per i campi in cui il conduttore è una potenza di due (rilevante per gli attuali standard NIST), $|\Delta_K| = d^d$. Di conseguenza, il termine logaritmico svanisce e il costo è dominato dal termine lineare $d-1$. Ciò implica che module-BKZ richiede una dimensione del blocco maggiore di circa $d-1$ per raggiungere la stessa pendenza di BKZ non strutturato. Questo conferma e quantifica la preoccupazione sollevata da Q8 in Kyber, suggerendo un leggero penalità di prestazione piuttosto che un'accelerazione.
  • Altri Campi Ciclotomici: Per i campi con fattori primi dispari nel loro conduttore (ad esempio, conduttori della forma $2^i \cdot 3^j$), $|\Delta_K| < d^d$. In questi casi, il termine logaritmico è negativo, producendo un guadagno sublineare nella dimensione del blocco richiesta ($\Theta(\beta / \ln \beta)$). Ciò si traduce in un'accelerazione subesponenziale nella complessità dell'attacco.
• Validazione Sperimentale: I dati sperimentali degli autori su vari campi ciclotomici ($\mathbb{Q}(\omega_3), \mathbb{Q}(\omega_4), \mathbb{Q}(\omega_{15}), \mathbb{Q}(\omega_{16})$) si allineano bene con le loro predizioni. I dati confermano che $\mathbb{Q}(\omega_3)$ e $\mathbb{Q}(\omega_{15})$ presentano profili più piatti (migliore riduzione) rispetto al baseline non strutturato, mentre $\mathbb{Q}(\omega_{16})$ (potenza di due) mostra un profilo peggiore.

Significato e Rivendicazioni
Il documento sostiene di essere il primo lavoro a fornire un'analisi concreta del caso medio di module-BKZ, andando oltre i limiti teorici del caso peggiore. La sua importanza risiede nel:

1. Risolvere Q8: Affronta direttamente la questione aperta sull'efficienza di module-BKZ sui campi ciclotomici potenza di due, concludendo che per questi campi specifici, la struttura modulare non fornisce un'accelerazione rispetto a BKZ non strutturato; anzi, comporta un piccolo sovraccarico (richiedendo una dimensione del blocco maggiore).
2. Identificare Costruzioni Alternative: Evidenzia che gli schemi basati su moduli di reticoli che utilizzano conduttori con piccoli fattori primi dispari (ad esempio, 3, 5) possono essere significativamente più deboli di quanto precedentemente pensato, poiché la struttura algebrica fornisce un'accelerazione subesponenziale per gli attacchi di riduzione di reticoli.
3. Strumentazione Pratica: Fornendo la prima implementazione open-source di module-BKZ, gli autori consentono ulteriori sperimentazioni e stime di sicurezza per gli schemi basati su moduli di reticoli.

Gli autori rimangono modesti riguardo alle loro rivendicazioni, notando che la loro analisi si basa su euristiche (come la Geometric Series Assumption adattata per i moduli) e che rimangono lacune nella modellazione dei fenomeni di "testa e coda" (head and tail) e nella velocità di convergenza dell'algoritmo. Dichiarano esplicitamente che i loro risultati non forniscono ancora un costo preciso per attacchi specifici, ma piuttosto un quadro predittivo per la pendenza della base ridotta.