Improving ML Attacks on LWE with Data Repetition and Stepwise Regression

1. Il Problema: Learning With Errors (LWE) e Attacchi ML

Il problema Learning With Errors (LWE) è alla base della maggior parte dei sistemi di crittografia post-quantistica (PQC). Si tratta di recuperare un vettore segreto $s$ dato un insieme di coppie $(a_i, b_i)$, dove $b_i = a_i \cdot s + \epsilon_i \pmod q$, con $\epsilon_i$ un piccolo errore gaussiano.

Sebbene LWE sia considerato difficile per segreti uniformi, varianti con secret sparsi (pochi bit non nulli) o piccoli (binari o ternari) sono attraenti per l'efficienza (es. crittografia omomorfa). Tuttavia, la sicurezza di queste varianti è sotto esame.
Attacchi precedenti basati sul Machine Learning (come SALSA, PICANTE, VERDE) hanno dimostrato di poter recuperare segreti, ma con un limite fondamentale: riescono a recuperare solo segreti con al massimo 3 bit "cruel" (non ridotti) dopo la riduzione reticolare BKZ.

• Cruel Region: Le prime coordinate del vettore $a$ che rimangono non ridotte dopo l'algoritmo BKZ.
• Cool Region: Le coordinate successive che vengono ridotte (varianza ridotta).
  Gli attacchi ML falliscono quando il numero di bit "cruel" attivi supera 3, a causa della difficoltà dei modelli nel gestire prodotti scalari modulari che "avvolgono" (wrap-around) molte volte il modulo $q$.

2. Metodologia Proposta

Gli autori propongono tre innovazioni principali per superare il limite dei 3 bit cruel e recuperare segreti con peso di Hamming ($h$) molto più elevato:

A. Dataset più grandi e Ripetizione dei Dati (Data Repetition)

Invece di addestrare il modello su un vasto set di dati unici, gli autori esplorano l'uso di set di addestramento più grandi con esempi ripetuti.

• Ispirazione: Studi precedenti (Charton & Kempe, 2024; Saxena et al., 2025) hanno mostrato che i Transformer possono apprendere operazioni modulari complesse (come la moltiplicazione o l'addizione modulare) con accuratezza del 100% se addestrati su piccoli set di dati ripetuti, invece che su grandi set di dati unici.
• Implementazione: Vengono generati fino a 400 milioni di campioni sintetici o ridotti tramite BKZ. Gli esempi vengono ripetuti ($R$ volte) durante l'addestramento per aiutare il modello a generalizzare meglio la relazione modulare.

B. Recupero dei Bit "Cool" con Regressione Stepwise

Una volta che i bit "cruel" sono stati stimati dal modello ML, i bit "cool" devono essere recuperati. I metodi precedenti usavano una regressione lineare standard, che presenta due difetti:

1. Ignora la natura modulare dell'operazione (sottostima i contributi dei bit non nulli che "avvolgono" il modulo).
2. Inverte una matrice di covarianza che contiene errori di campionamento, amplificando il rumore.

La soluzione proposta è la Regressione Stepwise (Efroymson, 1960):

• Meccanismo: Invece di stimare tutti i bit cool simultaneamente, il metodo identifica iterativamente il bit con il contributo più basso (assumendo che sia zero) e lo rimuove dal problema.
• Dual Stepwise Regression: Poiché i segreti sono sparsi, dopo aver eliminato molti zeri, i bit rimanenti sono prevalentemente 1. A questo punto, il metodo inverte il problema (dual problem): si assume che i bit rimanenti siano 1 e si cerca di trovare gli zeri tra quelli rimanenti, alternando tra recupero diretto e duale. Questo approccio sfrutta la sparsità e riduce l'accumulo di errori.

C. Architettura del Modello

Viene utilizzato un Transformer encoder-only (4 layer) con:

• Embedding Angolare: Per rappresentare i valori modulari.
• Embedding Posizionale Ibrido: Include una specifica indicazione binaria se una posizione appartiene alla regione "cruel" o "cool", migliorando la capacità del modello di distinguere le due zone.

3. Risultati Sperimentali

Gli esperimenti sono stati condotti su quattro configurazioni LWE diverse (con $n=256$ e $n=512$, e diversi valori di $\log_2 q$).

Punti chiave dei risultati:

• Superamento del limite dei 3 bit cruel: Gli autori riescono a recuperare segreti con fino a 8 bit cruel attivi, superando di gran lunga il limite precedente di 3.
• Peso di Hamming (h) recuperato:
  • Per $n=256, \log_2 q = 20$: Recupero di segreti con $h=70$ (confronto con $h=33$ di VERDE).
  • Per $n=512, \log_2 q = 41$: Recupero di segreti con $h=75$ (confronto con $h=63$ di VERDE e $h=60$ di Cool&Cruel).
• Effetto della Ripetizione: La ripetizione dei dati è cruciale. Per recuperare segreti difficili ($h=70$), non basta aumentare la quantità di dati unici; è necessaria una strategia di ripetizione ($R$) che modifichi la legge di scaling.
• Dati Sintetici vs BKZ: È stato dimostrato che i modelli addestrati su dati sintetici (generati con la stessa varianza dei dati ridotti BKZ) ottengono risultati identici a quelli addestrati su dati BKZ reali, riducendo drasticamente il costo computazionale.
• Legge di Scaling Empirica: Gli autori definiscono una legge di potenza empirica che lega il numero di tentativi necessari per il recupero ($A$) alla quantità di dati ($D$) e alla ripetizione ($R$):
  $$\ln(AR) = C_R - \alpha_R \ln(D)$$
  Dove $\alpha_R$ aumenta con la ripetizione, indicando che i dati ripetuti non solo riducono il bisogno di dati unici, ma cambiano la natura della scalabilità dell'attacco.

4. Contributi Chiave

1. Recupero di segreti più densi: Dimostrazione che gli attacchi ML possono recuperare segreti con fino a 8 bit cruel, superando i limiti imposti dalla regione "cruel" non ridotta.
2. Nuova tecnica di post-processing: Sostituzione della regressione lineare con la regressione stepwise (e duale) per il recupero dei bit cool, ottenendo prestazioni superiori.
3. Legge di Scaling: Definizione di una relazione empirica tra dimensione del dataset, ripetizione dei dati e successo dell'attacco, fornendo una guida per futuri attacchi su problemi LWE più difficili.
4. Validazione dei dati sintetici: Conferma che i dati sintetici possono sostituire i costosi dati ridotti BKZ per l'addestramento e lo studio delle leggi di scaling.

5. Significato e Implicazioni

Questo lavoro ha un impatto significativo sulla valutazione della sicurezza della crittografia post-quantistica:

• Vulnerabilità dei segreti sparsi: Dimostra che l'uso di segreti sparsi o piccoli in schemi basati su LWE potrebbe essere meno sicuro del previsto quando si utilizzano tecniche ML avanzate con grandi quantità di dati e strategie di ripetizione.
• Ottimizzazione degli Attacchi: Fornisce un nuovo paradigma per gli attacchi basati su ML, suggerendo che la "quantità" di dati non è l'unico fattore, ma la "strategia" di presentazione dei dati (ripetizione) è critica.
• Implicazioni per gli Standard: Poiché gli standard PQC (come Kyber/Dilithium) stanno venendo finalizzati, questi risultati sottolineano la necessità di considerare attentamente i parametri di sicurezza per le varianti con segreti sparsi, specialmente in scenari dove grandi quantità di dati di addestramento potrebbero essere disponibili.
• Limitazioni: L'attacco richiede risorse computazionali massicce per la generazione dei dati (anche se i dati sintetici mitigano questo) e si concentra su segreti binari/ternari sparsi. Tuttavia, la metodologia è potenzialmente adattabile ad altre varianti di LWE (Ring-LWE, Module-LWE).

In sintesi, il paper dimostra che i limiti attuali degli attacchi ML su LWE non sono intrinseci alla difficoltà matematica del problema, ma sono dovuti a limitazioni nelle strategie di addestramento e post-processing, che possono essere superate con dati ripetuti e regressione stepwise.