Fondamenti del Learning With Errors (LWE)

Learning With Errors (LWE) di Regev (2005): dati molti sistemi di equazioni lineari rumorose su Z_q, trovare il vettore segreto s. Il rumore e è piccolo, ma impedisce l'eliminazione gaussiana. Senza rumore, il sistema è facile da risolvere; anche con un rumore minimo, diventa computazionalmente difficile.

Segreto s ∈ Z_q^n. L'avversario riceve campioni (a_i, b_i), dove a_i ∈ Z_q^n è casuale, b_i = + e_i mod q ed e_i è un piccolo rumore tratto dalla distribuzione χ (ad esempio, una distribuzione gaussiana con σ = √n). Il compito è trovare s dati un numero polinomiale di campioni.

Senza rumore: b_i = mod q. L'eliminazione gaussiana recupera s in O(n^3). Con il rumore: anche una sola equazione errata compromette l'eliminazione. Il rumore è sufficientemente piccolo da consentire la decifratura usando la chiave, ma abbastanza grande da impedire la crittoanalisi.

Regev ha dimostrato che LWE si riduce, tramite una riduzione quantistica, a problemi sui reticoli nel caso peggiore (SIVP, GapSVP). Ciò significa che, se LWE viene violato, vengono risolti molti problemi difficili sui reticoli; tuttavia, non è noto alcun algoritmo quantistico per i problemi sui reticoli. LWE è sicuro nell'era post-quantistica.

RLWE sostituisce Z_q^n con l'anello Z_q[x]/(f(x)) per un polinomio ciclotomico f. Un singolo campione RLWE codifica n equazioni, con un'efficienza molto maggiore. RLWE costituisce la base di Kyber (KEM), Dilithium (firma) e degli schemi HE BFV/BGV/CKKS.

La sicurezza dipende da: n (dimensione, in genere 512-2048), q (modulo, 1024-2^60), σ (deviazione standard del rumore). Un n più grande e un rapporto σ/q più piccolo rendono il problema più difficile. Gli standard post-quantistici NIST usano n=256 (dimensione del modulo) con k moduli (k=2,3,4).

Chiave pubblica: (A, b=As+e). Per cifrare il bit m: scegliere r casuale e calcolare il testo cifrato (u=A^T r, v = b^T r + m*q/2). Decifrare: v - s^T u = e^T r + m*q/2 ≈ m*q/2. Arrotondare al valore di m più vicino. Il rumore e mantiene m nascosto nel testo cifrato durante la cifratura.

Decision-LWE: distinguere (a, As+e) da (a, u), dove u è uniforme e casuale. Sono computazionalmente indistinguibili assumendo la difficoltà di LWE. Questa è la base della sicurezza semantica: per gli avversari privi della chiave segreta, i testi cifrati appaiono come rumore casuale.

I migliori attacchi noti utilizzano la riduzione dei reticoli BKZ (Block Korkine-Zolotarev). La complessità è subesponenziale, ma non polinomiale. BKZ-β richiede 2^{0.292β} operazioni. Per LWE-512, la sicurezza contro BKZ è di circa 128 bit. Non è nota alcuna accelerazione quantistica per BKZ.

Module-LWE (utilizzato in Kyber) è RLWE su moduli di rango k. Offre flessibilità: k=2 per una sicurezza di 512 bit, k=3 per 768 bit, k=4 per 1024 bit. La sicurezza e le prestazioni aumentano con k. NIST ha selezionato Kyber (ribattezzato ML-KEM) come standard PQC.

La sicurezza di RSA/ECC si basa sulla fattorizzazione di interi e sul logaritmo discreto, vulnerabili ai computer quantistici tramite Shor. La sicurezza di LWE si basa su problemi difficili nel caso peggiore sui reticoli, per i quali non è nota alcuna accelerazione quantistica. Dimensioni delle chiavi: chiavi LWE di circa 1 KB contro i 256 byte di RSA-2048. LWE è più grande, ma resistente ai computer quantistici.

Cosa rende difficile risolvere LWE anche disponendo di molti campioni?

LWE: trovare il segreto s a partire da equazioni lineari rumorose, un problema difficile per i computer quantistici. RLWE utilizza anelli polinomiali per una maggiore efficienza. Costituisce la base di Kyber, Dilithium e degli schemi HE. Prossimo argomento: gli schemi HE BGV e BFV per le operazioni su interi.