ImplementazioneImplementazione

Riepilogo

Kyber è progettato per essere implementato efficientemente sia in software che in hardware. Le sue operazioni principali sono moltiplicazioni polinomiali in R_q = Z_q[x]/(x^n + 1) con n = 256, q = 3329.

NTT — Number Theoretic Transform

La moltiplicazione in R_q è l'operazione dominante. Kyber la accelera usando NTT, l'analogo della FFT in campi finiti.

Moltiplicazione ingenua: O(n²) = 65,536 operazioni
Moltiplicazione via NTT: O(n log n) ≈ 2,048 operazioni

L'NTT in Kyber usa radici primitive dell'unità in Z_q. Poiché q = 3329 è primo e 3329 ≡ 1 (mod 512), esiste una radice primitiva di ordine 512, necessaria per NTT con n = 256.

La Trasformata

Kyber non NTT-trasforma tutti i polinomi. Un'ottimizzazione chiave è mantenere alcuni polinomi in dominio NTT (già trasformati) per evitare trasformazioni non necessarie:

• Â (la matrice pubblica trasformata) viene memorizzata in dominio NTT
• ŝ (la chiave segreta trasformata) viene anch'essa memorizzata in dominio NTT
• L'incapsulamento richiede trasformare s' al dominio NTT e ritrasformare u

Questo riduce il numero di NTT inversi necessari.

Compress e Decompress

Kyber comprime i ciphertext scartando bit di bassa magnitudine. Questo riduce la dimensione di ct ma introduce errore di compressione — errore che si somma all'errore crittografico e deve essere gestito dai parametri.

Compress_q(x, d) = ⌈(2^d / q) · x⌋ mod 2^d
Decompress_q(y, d) = ⌈(q / 2^d) · y⌋

Dove d controlla la precisione: più bit → meno errore di compressione → ciphertext più grande.

La compressione non è simmetrica: Decompress(Compress(x)) ≈ x ma non uguale. La differenza deve essere assorbita dal margine di errore dello schema.

FO Transform — Fujisaki-Okamoto

La trasformazione FO è ciò che converte un PKE (cifratura asimmetrica) insicuro contro attacchi adattivi in un KEM CCA-sicuro.

Il PKE sottostante di Kyber (senza FO) è CPA-sicuro ma non CCA-sicuro. Senza FO, un attaccante potrebbe:

1. Intercettare un ciphertext ct
2. Modificarlo leggermente → ct'
3. Osservare se il ricevente accetta ct' o no (oracolo di validità)
4. Usare quella informazione per recuperare la chiave

FO elimina questo facendo sì che la decifratura rielabori il ciphertext ricevuto e verifichi che coincida con quello che verrebbe generato da zero con la stessa moneta casuale. Se non coincide, viene restituita una chiave pseudo-casuale (non quella reale).

FO implicito vs esplicito

Kyber usa FO implicito: non restituisce un simbolo di rifiuto distinguibile, ma una chiave falsa. Questo evita attacchi di oracolo che dipendono dalla distinzione tra "fallimento" e "successo".

Decaps(sk, ct):
    m' = Decrypt(sk, ct)          # decifrare
    (K', r') = G(m' || H(pk))     # rielaborare
    ct' = Encrypt(pk, m', r')     # re-cifrare
    if ct' == ct:
        return K'                 # reale
    else:
        return H(sk || ct)        # pseudo-casuale (indistinguibile)

Campionamento Deterministico di A

La matrice A viene generata da un seed d usando SHAKE-128 come generatore di numeri casuali estendibile (XOF). Questo significa che:

1. A non deve essere memorizzata nella chiave pubblica (si memorizza solo il seed, 32 byte).
2. Chiunque può ricostruire A conoscendo il seed.
3. La generazione è deterministica: stesso seed → stessa matrice.

Il seed è incluso in pk come parte degli 800/1184/1568 byte.

Ottimizzazioni

Software

Hardware

Implementazioni di Riferimento

Riferimenti

• Bos, J. et al. (2018). "CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM."
• Alkim, E. et al. (2020). "The Number Theoretic Transform and Its Applications in Lattice-Based Cryptography."
• Montgomery, P. (1985). "Modular Multiplication Without Trial Division." Mathematics of Computation.