Ring-LWE e reticoli modulari

LWE standard richiede prodotti matrice-vettore di grandi dimensioni, con conseguenti chiavi di grandi dimensioni. Ring-LWE, introdotto da Lyubashevsky, Peikert e Regev nel 2010, sostituisce vettori e matrici con polinomi nell’anello R_q = Z_q[X]/(f(X)). Questa struttura consente di ottenere chiavi molto più compatte e operazioni aritmetiche più veloci, diventando il fondamento pratico della crittografia reale basata sui reticoli.

Il polinomio f(X) utilizzato in Ring-LWE è generalmente f(X) = X^n + 1, dove n è una potenza di 2. Si tratta del polinomio ciclotomico 2n-esimo. Viene scelto perché è irriducibile su Z, garantisce buone proprietà algebriche dell’anello R_q e consente di utilizzare la trasformata teorica dei numeri (NTT) per una moltiplicazione efficiente. Gli anelli ciclotomici sono stati studiati approfonditamente e sono ritenuti sicuri.

In Ring-LWE, il segreto s è un polinomio in R_q e i campioni hanno la forma (a, b = a*s + e), dove a è un elemento casuale uniforme dell’anello ed e è un piccolo polinomio di errore. L’avversario osserva molti campioni di questo tipo e deve recuperare s oppure distinguerli da campioni uniformi. La difficoltà si basa sull’ipotesi Ring-LWE, che dispone di una riduzione da problemi nel caso peggiore su reticoli ideali.

Ring-LWE è più difficile da attaccare, ma presenta anche una riduzione di sicurezza leggermente diversa rispetto a LWE standard. La riduzione parte da problemi nel caso peggiore su reticoli ideali (ideal-SVP), non da reticoli arbitrari. In linea di principio, la struttura aggiuntiva dei reticoli ideali potrebbe renderli più facili dei reticoli generali, ed è un tema di ricerca attivo. Non è noto alcun attacco pratico che sfrutti questa struttura.

Module-LWE (M-LWE) generalizza sia LWE sia Ring-LWE operando con una matrice k x k di elementi dell’anello, anziché con un singolo elemento dell’anello o con una grande matrice di interi. Quando k = 1, si riduce a Ring-LWE; all’aumentare di k, si avvicina a LWE standard. Questo parametro k regolabile consente di bilanciare la fiducia nella sicurezza e le prestazioni.

CRYSTALS-Kyber, ora ML-KEM (FIPS 203), si basa su Module-LWE con una matrice di rango k su R_q. Il parametro k controlla direttamente il livello di sicurezza: k=2 punta a una sicurezza di 128 bit (ML-KEM-512), k=3 a 192 bit (ML-KEM-768) e k=4 a 256 bit (ML-KEM-1024). La struttura a moduli consente di utilizzare un’unica base di codice e di aumentare la sicurezza modificando k.

La moltiplicazione di polinomi in R_q = Z_q[X]/(X^n + 1) costituisce il principale collo di bottiglia in termini di prestazioni. La trasformata teorica dei numeri (NTT) è una trasformata discreta di Fourier su Z_q che converte i polinomi nella forma di valutazione, dove la moltiplicazione diventa puntuale. Scegliendo q in modo che sia possibile applicare la NTT, la moltiplicazione dei polinomi richiede tempo O(n log n) invece di O(n^2), un’ottimizzazione fondamentale in ML-KEM e ML-DSA.

La NTT richiede che q sia un primo tale che q = 1 mod 2n, garantendo che Z_q contenga una radice primitiva 2n-esima dell’unità. Per ML-KEM con n = 256, q = 3329 soddisfa questo requisito. La NTT su Z_3329 è estremamente veloce sull’hardware moderno con istruzioni SIMD e consente di eseguire migliaia di operazioni ML-KEM al secondo su CPU comuni.

Ring-LWE e Module-LWE riducono drasticamente le dimensioni delle chiavi rispetto a LWE standard. Una chiave pubblica LWE standard per 128 bit di sicurezza potrebbe avere una dimensione di 1 MB; Ring-LWE la riduce a circa 800 byte, mentre Module-LWE (ML-KEM-768) raggiunge una chiave pubblica di 1184 byte con 192 bit di sicurezza post-quantistica. Questa compattezza rende gli schemi basati su reticoli pratici per TLS e i sistemi embedded.

Alcuni crittografi temono che la struttura algebrica aggiuntiva degli anelli ciclotomici possa consentire attacchi non applicabili a LWE semplice. Nel 2024, Elias Rokicki e i suoi collaboratori hanno pubblicato un'analisi del polinomio ciclotomico di ordine 2n, senza individuare exploit pratici, ma sottolineando l'importanza di continuare a esaminarlo. Il processo PQC di NIST ha preso in considerazione questo rischio e ha scelto Module-LWE anche per ridurre la dipendenza da un'unica struttura ad anello.

Oltre a Kyber, Ring-LWE è alla base di CRYSTALS-Dilithium (ML-DSA), lo schema di firma standardizzato da NIST. La libreria SEAL di Microsoft consente la cifratura omomorfica tramite Ring-LWE. La libreria di crittografia Tink di Google include il supporto per ML-KEM. Ring-LWE è passato dalla costruzione teorica alla distribuzione in produzione in un tempo sorprendentemente breve, grazie al processo di standardizzazione di NIST.

Qual è il principale vantaggio di Ring-LWE rispetto a LWE standard?

Ring-LWE trasferisce LWE nell'anello dei polinomi R_q = Z_q[X]/(X^n+1), riducendo drasticamente le dimensioni delle chiavi e consentendo un'aritmetica rapida basata su NTT. Module-LWE generalizza questo approccio con una struttura di rango-k, alla base di ML-KEM (FIPS 203) e ML-DSA (FIPS 204). Il primo q = 3329, adatto a NTT, consente un'implementazione efficiente. La sicurezza si basa sulla difficoltà dei problemi nei reticoli ideali e modulari.