Riepilogo
Kyber basa la sua sicurezza sul problema Module-LWE (Learning With Errors su moduli), una variante del LWE classico definito da Regev nel 2005. Comprendere LWE è comprendere perché Kyber è sicuro e, più importante, fin quando potrebbe esserlo.
Il Problema LWE
Dato un segreto s, una matrice A e un vettore di errori e:
s = vettore segreto (dimensione n)
A = matrice casuale (m × n)
e = vettore di errore piccolo (campionato da una distribuzione χ)
b = A·s + e (modulo q)
Problema di ricerca (Search-LWE): Dati (A, b), trovare s.
Problema di decisione (Decision-LWE): Dati (A, b), distinguere se b = A·s + e o se b è uniformemente casuale.
La sicurezza dipende dal fatto che, sebbene A·s sia deterministico, l'errore e rende il sistema difficilmente invertibile. Senza e, sarebbe algebra lineare banale.
Perché è duro
Recuperare s da (A, b) è equivalente a risolvere problemi di reticoli (lattices) che sono NP-duri nel caso peggiore. La riduzione di Regev (2005) ha mostrato che rompere LWE è almeno tanto duro quanto certi problemi di reticoli nel caso peggiore (GapSVP, SIVP).
Module-LWE
Kyber usa Module-LWE, dove A e s non sono interi scalari ma elementi di un modulo su un anello di polinomi:
R_q = Z_q[x] / (x^n + 1)
Dove n = 256 per Kyber. La matrice A ha entrate in R_q e dimensione k × k (dove k = 2, 3, 4 secondo il livello di sicurezza).
A ∈ R_q^{k×k}, s ∈ R_q^{k}, e ∈ R_q^{k}
b = A·s + e
Vantaggio rispetto a LWE standard: Module-LWE offre un equilibrio tra efficienza (gli anelli permettono moltiplicazione rapida via NTT) e sicurezza (il modulo k controlla la dimensione senza crescere al quadrato).
Perché modulo e non anello completo?
Ring-LWE (usato da NewHope, per esempio) opera su un singolo anello (R_q). Module-LWE interpola tra LWE standard e Ring-LWE:
| Schema | Dimensione | Efficienza | Sicurezza conservativa |
|---|---|---|---|
| LWE standard | n × k |
Bassa | Alta |
| Ring-LWE | n |
Alta | Media |
| Module-LWE | n × k |
Alta | Alta |
La Distribuzione di Errore
Kyber usa una distribuzione binomiale centrata CBD(η) invece di una gaussiana discreta. Questo semplifica l'implementazione (non richiede campionamento da tabella) e evita attacchi di temporizzazione.
Pr[ e = x ] = (C(2η, η+x)) / 2^(2η)
Per ML-KEM-512: η = 2. Per ML-KEM-768 e 1024: η = 3.
Il Modulo q = 3329
La scelta di q = 3329 non è accidentale:
- È un primo tale che
q ≡ 1 (mod 2n)pern = 256, il che permette di usare NTT (Number Theoretic Transform) per moltiplicazione rapida inR_q. - È abbastanza piccolo perché ciphertext e chiavi siano compatti.
- È abbastanza grande perché l'errore non trabocchi e causi decifrature errate.
La Congettura Centrale
La sicurezza di Kyber (e di tutta la crittografia basata su reticoli) poggia sulla congettura che:
Non esiste un algoritmo quantistico (né classico) che risolva Module-LWE per i parametri di Kyber in tempo polinomiale.
Questa congettura è plausibile ma non dimostrata. La storia della crittografia insegna che le congetture di durezza a volte falliscono. Ciò che distingue LWE da RSA/ECC è che non si conosce un analogo quantistico di Shor per i reticoli — ma questo non significa che non possa essere scoperto.
Riferimenti
- Regev, O. (2005). "On lattices, learning with errors, random linear codes, and cryptography." STOC 2005.
- Bos, J. et al. (2018). "CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM." EuroS&P 2018.
- Langlois, A. & Stehlé, D. (2015). "Worst-case to average-case reductions for module lattices." Designs, Codes and Cryptography.