Learning With Errors: il problema difficile

Il problema Learning With Errors (LWE) è stato introdotto da Oded Regev nel 2005 come fondamento della crittografia post-quantistica. Data una matrice casuale A su Z_q e un vettore b = As + e, l’obiettivo è trovare il vettore segreto s. Il vettore e è un errore di piccola entità estratto da una distribuzione gaussiana discreta, che rende il problema computazionalmente intrattabile.

Nel problema LWE, A è una matrice casuale m x n campionata uniformemente su Z_q, dove q è un modulo primo. Il segreto s è un vettore n-dimensionale ed e è un piccolo vettore di errore i cui elementi sono estratti da una distribuzione gaussiana stretta. Anche conoscendo la struttura di A, un avversario non può distinguere b da un vettore uniformemente casuale.

Esistono due formulazioni standard di LWE. LWE di ricerca richiede di recuperare il segreto s a partire da molti campioni (A, b). LWE decisionale richiede di distinguere i campioni (A, As + e) da coppie casuali uniformi (A, u). Le due formulazioni sono equivalenti in tempo polinomiale: un algoritmo che risolve una può essere trasformato in uno che risolve l’altra.

Il termine di errore in LWE è estratto da una distribuzione gaussiana discreta sugli interi, parametrizzata dalla deviazione standard sigma. Valori piccoli di sigma fanno sì che e sia piccolo rispetto a q, facendo apparire b quasi uguale ad As mod q. Se sigma fosse zero, non ci sarebbe alcun errore e il sistema potrebbe essere risolto mediante eliminazione di Gauss; perciò l’errore è essenziale per la difficoltà del problema.

Regev ha dimostrato una riduzione notevole: risolvere campioni LWE nel caso medio è difficile almeno quanto risolvere istanze nel caso peggiore del problema del vettore più corto (SVP) sui reticoli. Ciò significa che, se fosse possibile violare LWE in modo efficiente, sarebbe possibile risolvere in modo efficiente qualsiasi problema sui reticoli. Non è noto alcun algoritmo classico o quantistico in grado di risolvere SVP nel caso peggiore in tempo polinomiale.

A differenza della crittografia RSA e a curve ellittiche, non è noto alcun algoritmo quantistico che offra un’accelerazione esponenziale contro LWE. L’algoritmo di Grover offre al massimo un’accelerazione quadratica, mentre i migliori algoritmi quantistici per i reticoli, varianti di BKZ, non violano LWE con parametri scelti correttamente. Ciò rende LWE una solida base per la sicurezza post-quantistica.

La sicurezza di LWE è determinata da tre parametri: la dimensione n, cioè la lunghezza del segreto, il modulo q e la deviazione standard dell’errore sigma. Valori maggiori di n e un rapporto q/sigma più piccolo aumentano la sicurezza. Per una sicurezza post-quantistica di 128 bit, i valori tipici sono n = 1024, q circa 12289 e sigma circa 3.2. Lo strumento lattice estimator di Albrecht et al. viene utilizzato per valutare la sicurezza concreta.

Il problema della soluzione intera corta (SIS) è un’ipotesi di difficoltà sui reticoli correlata, utilizzata per le firme. Data una matrice casuale A su Z_q, occorre trovare un vettore x corto e diverso da zero tale che Ax = 0 mod q. SIS è alla base delle funzioni hash e degli schemi di firma nel mondo dei reticoli e completa LWE, che è alla base della cifratura e dell’incapsulamento delle chiavi.

Un semplice schema di cifratura LWE funziona nel modo seguente: la chiave pubblica è (A, b = As + e) e la chiave segreta è s. Per cifrare un bit m, il mittente calcola (u, v) = (A^T r, b^T r + m * floor(q/2)) per un vettore binario casuale r. La decifratura calcola v - s^T u e arrotonda il risultato per recuperare m. Questo schema raggiunge la sicurezza IND-CPA sotto l’ipotesi LWE.

LWE ha reso possibili numerose costruzioni crittografiche oltre alla cifratura di base. Tra queste figurano la cifratura completamente omomorfica (FHE), la cifratura basata sull’identità (IBE), la cifratura basata sugli attributi (ABE) e i protocolli di scambio delle chiavi. CRYSTALS-Kyber, ora ML-KEM, standardizzato come FIPS 203, è lo schema basato su LWE più diffuso nelle applicazioni pratiche.

La crittografia basata su LWE sta già entrando nei sistemi di produzione. Google e Cloudflare hanno condotto esperimenti TLS utilizzando Kyber tra il 2018 e il 2020. Nel 2024 Chrome e Firefox hanno aggiunto il supporto per ML-KEM-768 negli handshake TLS ibridi. Il Signal Protocol ha aggiunto un livello post-quantistico (PQXDH) che utilizza ML-KEM-1024 per la segretezza in avanti, proteggendo la riservatezza a lungo termine dei messaggi dai futuri computer quantistici.

Quale affermazione descrive meglio la garanzia di difficoltà del problema LWE?

LWE è una delle ipotesi di difficoltà post-quantistiche più studiate ed è sostenuta da una solida riduzione dal caso peggiore relativa ai problemi sui reticoli. I suoi tre parametri (n, q, sigma) determinano il compromesso tra sicurezza e prestazioni. LWE resiste agli attacchi quantistici ed è alla base degli schemi standardizzati da NIST. Comprendere LWE è il punto di partenza per tutta la moderna crittografia basata sui reticoli, inclusi ML-KEM e ML-DSA.