Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs

1. Problema e Contesto

Il lavoro si concentra sulla sicurezza dei problemi Learning With Errors (LWE) e Learning Parity with Noise (LPN) nella loro variante sparsa (k-sparse) e su moduli più alti ($q > 2$).

• LWE/LWE Sparsa: In LWE standard, i campioni sono coppie $(a, \langle a, s \rangle + e)$ dove $a$ è uniforme. Nella versione sparsa, il vettore $a$ ha solo $k$ voci non nulle (con $k \ll n$). Questa sparsità è desiderabile per l'efficienza computazionale e di memorizzazione, ma pone interrogativi sulla sua durezza rispetto alla versione densa.
• Obiettivo: Determinare la complessità computazionale (trade-off tra numero di campioni $m$ e tempo di esecuzione) per distinguere un'istanza "piantata" (con segreto e rumore) da una distribuzione uniforme casuale.
• Stato dell'arte: Precedenti lavori (es. Wein et al., Gupta et al.) avevano risolto il caso $q=2$ (k-XOR) utilizzando il metodo Kikuchi. Il lavoro di Jain, Lin e Saha (JLS24) aveva analizzato LWE sparsa su moduli grandi, ma le loro tecniche di attacco (vettori sparsi nel nucleo, minori densi) richiedevano tempo esponenziale per parametri realistici, portando alla congettura che LWE sparsa fosse dura quanto LWE standard.

2. Metodologia: Generalizzazione del Metodo Kikuchi

Gli autori generalizzano il metodo Kikuchi, originariamente sviluppato per $q=2$, per gestire moduli $q$ arbitrari (e in particolare primi). La metodologia si articola in tre fasi principali:

A. Costruzione del Grafo Kikuchi per $k$-LIN$_q$

Il problema $k$-LIN$_q$ (sistema di equazioni lineari sparse su $\mathbb{Z}_q$) viene trasformato in un problema di equazioni prodotto su radici dell'unità complesse $\Omega_q = \{e^{2\pi i s/q}\}$.

• Spazio degli stati: Invece di considerare sottoinsiemi di indici (come per $q=2$), lo spazio viene elevato a dimensioni superiori: sottoinsiemi di coppie (indice, coefficiente) di dimensione $l$ (dove $k/2 \le l \le n$). Lo spazio dei vertici del grafo è $N = \binom{n}{l} \times q^l$.
• Architettura del Grafo: Il grafo Kikuchi $K_l(I)$ è un grafo diretto (diverso dal caso non diretto per $q=2$). Per ogni vincolo $(S, b)$, si aggiungono archi tra vertici $T_1$ e $T_2$ se la loro "differenza generalizzata" corrisponde al supporto del vincolo $S$.
• Simmetria: Per garantire proprietà spettrali utili, per ogni arco $T_1 \xrightarrow{b} T_2$, viene aggiunto l'arco inverso $T_2 \xrightarrow{b^*} T_1$, rendendo la matrice di adiacenza Ermiteana.

B. Due Strategie di Attacco

Il paper propone due approcci distinti per distinguere le istanze, basati su proprietà diverse del grafo Kikuchi:

1. Metodo Spettrale (Spectral Method):

   • Concetto: Si calcola la norma spettrale (il più grande autovalore in modulo) della matrice di adiacenza del grafo Kikuchi.
   • Logica: Per un'istanza casuale, la norma spettrale è piccola (intorno a 0). Per un'istanza piantata, la presenza del segreto crea una "correlazione" che alza la norma spettrale a un valore proporzionale alla densità media del grafo e al parametro di rumore.
   • Strumenti: Utilizza la disuguaglianza di Bernstein per matrici (Matrix Bernstein) per derivare limiti di coda (tail bounds) per le distribuzioni casuale e piantata.
   • Vantaggi: Funziona per qualsiasi distribuzione di rumore (purché concentrata su 0) e non richiede che $q$ sia primo.

2. Metodo dei Coperture q-ary (q-ary Cover Method):

   • Concetto: Generalizza il concetto di "even cover" (copertura pari) usato per $q=2$. Una q-ary cover è un multinsieme di vincoli tali che la somma dei coefficienti di ogni variabile sia $0 \pmod q$.
   • Ricerca: Si trovano queste coperture cercando cammini chiusi (closed walks) nel grafo Kikuchi. Un cammino chiuso corrisponde a una combinazione lineare di vincoli che annulla le variabili.
   • Logica:
     • Per LPN (rumore uniforme su $\mathbb{Z}_q \setminus \{0\}$): Si analizza il prodotto dei termini di destra dei vincoli nella copertura. Grazie alle proprietà di anti-concentrazione dei polinomi multilineari, il valore atteso è diverso tra caso casuale e piantato.
     • Per LWE (rumore Gaussiano limitato): Si sfrutta il fatto che il rumore è limitato. Se si trova una copertura $c$ tale che $c^T A = 0$, allora $c^T \beta = c^T e$. Poiché $e$ è piccolo, $|c^T \beta|$ sarà piccolo nel caso piantato, mentre sarà uniforme (e quindi grande) nel caso casuale.
   • Vantaggi: Offre un miglioramento quadratico quasi rispetto al metodo spettrale per lo stesso numero di campioni e funziona anche se i lati sinistri delle equazioni non sono uniformi (caso worst-case).

3. Risultati Principali (Teoremi)

Gli autori stabiliscono nuovi trade-off tra complessità dei campioni ($m$) e complessità temporale ($T$) in funzione del parametro di trade-off $l$.

• Attacco Spettrale (LWE/LPN):

  • Tempo: $\tilde{O}\left( \binom{n}{l} q^l \right)$.
  • Campioni richiesti: $m \ge \Omega\left( \binom{n}{l} q^l \right)$ (con fattori logaritmici).
  • Questo generalizza i risultati di Wein et al. e Gupta et al. a moduli grandi.

• Attacco q-ary Cover (LWE/LPN):

  • Tempo: $\tilde{O}\left( \sqrt{\binom{n}{l} q^l} \cdot (n/l)^k \right)$ (per LPN e LWE con condizioni su $q$).
  • Campioni richiesti: Simili al metodo spettrale, ma con un tempo di esecuzione significativamente ridotto (quasi quadratico) quando $l \gg k$.
  • Condizioni: Richiede che $q$ sia primo e, per LWE, che $q$ sia sufficientemente grande rispetto al rumore ($q \gg r(l \log n)^{3/2}$).

Implicazioni sulla Congettura di JLS24:
Il lavoro dimostra che se si accetta un tempo esponenziale arbitrariamente piccolo ($2^{\delta n}$), è possibile risolvere LWE sparsa con un numero di campioni polinomiale (o quasi polinomiale) quando la sparsità $k$ è $O(\log n / \log \log n)$. Questo "chiude il gap" sulla congettura di JLS24, suggerendo che la durezza di LWE sparsa è strettamente legata a quella di LWE standard solo per parametri specifici, ma può essere violata con un piccolo sacrificio temporale.

4. Contributi Chiave

1. Generalizzazione a Moduli Arbitrari: Estensione del metodo Kikuchi da $q=2$ a $q > 2$, gestendo la complessità dei coefficienti e delle radici dell'unità.
2. Nuovi Trade-off: Introduzione di un parametro $l$ che permette di bilanciare flessibilmente campioni e tempo, superando i limiti delle tecniche precedenti.
3. Miglioramento Temporale: Il metodo delle coperture q-ary offre un'accelerazione quasi quadratica rispetto al metodo spettrale per la stessa quantità di campioni.
4. Analisi di Robustezza: Dimostrazione che il metodo spettrale è robusto rispetto alla distribuzione del rumore, mentre il metodo delle coperture è efficace per casi worst-case (distribuzioni non uniformi dei lati sinistri).
5. Confronto Quantistico: Viene menzionato che il metodo spettrale ammette un'accelerazione quantistica (da quadratica a quartica), mentre per il metodo delle coperture non è ancora nota un'accelerazione quantistica.

5. Significato e Impatto

Questo lavoro è fondamentale per la crittografia basata su reticoli perché:

• Valutazione della Sicurezza: Fornisce parametri precisi per valutare la sicurezza di schemi crittografici che utilizzano LWE/LPN sparsi su moduli grandi (comuni in schemi avanzati come FHE - Fully Homomorphic Encryption).
• Raffinamento delle Ipotesi di Durezza: Sposta la comprensione della durezza di LWE sparsa da un'ipotesi binaria (dura o non dura) a una più sfumata, dipendente dai parametri di sparsità e dal numero di campioni disponibili.
• Metodologia Unificata: Offre un quadro teorico unificato per analizzare problemi di apprendimento con errori su strutture sparse, collegando tecniche spettrali e combinatorie.

In sintesi, il paper dimostra che le varianti sparse di LWE e LPN su moduli grandi non sono intrinsecamente più sicure della versione densa se si dispone di un numero sufficiente di campioni e di un tempo di calcolo leggermente superiore al polinomiale, fornendo nuovi algoritmi di attacco che sfruttano la struttura sparsa in modo più efficiente rispetto alle tecniche precedenti.