Struttura del KEMStruttura del KEM

Riepilogo

Kyber è un Key Encapsulation Mechanism (KEM), non uno schema di cifratura asimmetrica generale. Un KEM permette a due parti di concordare una chiave simmetrica condivisa senza scambiarla esplicitamente. Per cifrare dati, si usa la chiave derivata con una cifratura simmetrica (AES, ChaCha).

Componenti

Un KEM ha tre operazioni:

G = KeyGen()             → (pk, sk)
E = Encaps(pk)           → (ct, K)
D = Decaps(sk, ct)       → K

KeyGen — Generazione delle Chiavi

1. Generare seed casuale d (32 byte)
2. Derivare A ∈ R_q^{k×k} da d usando SHAKE-128 (campionamento deterministico)
3. Campionare s ∈ R_q^{k} dalla distribuzione CBD(η)
4. Campionare e ∈ R_q^{k} dalla distribuzione CBD(η)
5. Calcolare pk = A·s + e    (codificato come byte array)
6. Memorizzare sk = (s, pk)   (o una forma hash per disincapsulamento più veloce)
7. Restituire (pk, sk)

Notevole: La matrice A viene generata in modo deterministico da un seed. Questo significa che A non deve essere memorizzata né trasmessa — chiunque conosca il seed può ricostruirla.

Encaps — Incapsulamento

Input: pk

1. Generare una moneta casuale m (32 byte)
2. Derivare (K, r) = G(m || H(pk))   usando SHA3-256/SHAKE256
   dove G è un hash, H è un altro hash
3. Calcolare t = H(m)                  (commitment implicito)
4. Cifrare m usando pk e la casualità r:
   a. Campionare s' ∈ R_q^{k} da CBD(η) usando r
   b. Campionare e1 ∈ R_q^{k} da CBD(η)
   c. Campionare e2 ∈ R_q da CBD(η)
   d. Calcolare u = NTT^{-1}(·NTT(s')) + e1
   e. Calcolare v = NTT^{-1}(t^T·NTT(s')) + e2 + Decompress_q(m, 1)
5. Restituire ct = (u, v)   e   K

Decaps — Disincapsulamento

Input: sk, ct = (u, v)

1. Decifrare:
   a. m' = Compress_q(v - s^T·u, 1)
2. Rielaborare:
   a. (K', r') = G(m' || H(pk))
   b. Rieseguire Encaps usando m' e r'
   c. Confrontare risultato con ct ricevuto
3. Se coincide: restituire K'
   Se non coincide: restituire chiave pseudo-casuale derivata da (sk, ct)

Il passo di rielaborazione e confronto (Fujisaki-Okamoto transform) è ciò che rende Kyber CCA-sicuro. Senza di esso, il KEM sarebbe vulnerabile ad attacchi di testo cifrato adattivo.

Il Flusso Completo

Alice                          Bob
  |                              |
  |--- (pk = A·s + e) --------->|  (KeyGen di Alice)
  |                              |
  |<--- (ct = (u,v), K) --------|  (Encaps usando pk di Alice)
  |                              |
  |--- decifra ct con s --------|  (Decaps: recupera K)
  |                              |
  |--- (usa K per AES/ChaCha) --|  (comunicazione cifrata)

Importante: A differenza di RSA o ECDH, in Kyber il ricevente genera la coppia di chiavi e il mittente genera il ciphertext e la chiave. È asimmetrico nelle direzioni: l'incapsulamento va sempre dal mittente al ricevente.

Perché KEM e non cifratura diretta?

La decisione di NIST di standardizzare KEM invece di PKE (cifratura asimmetrica diretta) risponde a:

1. Semplicità: Un KEM ha un'interfaccia più piccola e meno modi di fallimento.
2. Ibrido naturale: Kyber + AES/ChaCha = cifratura ibrida, che è la pratica raccomandata anche con RSA/ECC.
3. FO transform gestibile: La trasformazione di Fujisaki-Okamoto da un PKE a un KEM CCA-sicuro è più facile da analizzare e verificare rispetto a un PKE CCA-sicuro diretto.

Per cifratura asimmetrica di uso generale, si usa HPKE (Hybrid Public Key Encryption, RFC 9180), che definisce come combinare un KEM con un AEAD. HPKE con Kyber è già in fase di standardizzazione.

Riferimenti

• Fujisaki, E. & Okamoto, T. (1999). "Secure Integration of Asymmetric and Symmetric Encryption Schemes." CRYPTO 1999.
• Hofheinz, D., Hövelmanns, K. & Kiltz, E. (2017). "A Modular Analysis of the Fujisaki-Okamoto Transformation." TCC 2017.
• RFC 9180 — Hybrid Public Key Encryption (HPKE).