KEM Structure

Summary

Kyber is a Key Encapsulation Mechanism (KEM), not a general asymmetric encryption scheme. A KEM allows two parties to agree on a shared symmetric key without explicitly exchanging it. To encrypt data, the derived key is used with a symmetric cipher (AES, ChaCha).

Components

A KEM has three operations:

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

KeyGen — Key Generation

1. Generate random seed d (32 bytes)
2. Derive A ∈ R_q^{k×k} from d using SHAKE-128 (deterministic sampling)
3. Sample s ∈ R_q^{k} from the CBD(η) distribution
4. Sample e ∈ R_q^{k} from the CBD(η) distribution
5. Compute pk = A·s + e    (encoded as byte array)
6. Store sk = (s, pk)      (or a hash form for faster decapsulation)
7. Return (pk, sk)

Notable: The matrix A is generated deterministically from a seed. This means A does not need to be stored or transmitted — anyone who knows the seed can reconstruct it.

Encaps — Encapsulation

Input: pk

1. Generate a random coin m (32 bytes)
2. Derive (K, r) = G(m || H(pk))   using SHA3-256/SHAKE256
   where G is one hash, H is another hash
3. Compute t = H(m)                  (implicit commitment)
4. Encrypt m using pk and randomness r:
   a. Sample s' ∈ R_q^{k} from CBD(η) using r
   b. Sample e1 ∈ R_q^{k} from CBD(η)
   c. Sample e2 ∈ R_q from CBD(η)
   d. Compute u = NTT^{-1}(Â·NTT(s')) + e1
   e. Compute v = NTT^{-1}(t^T·NTT(s')) + e2 + Decompress_q(m, 1)
5. Return ct = (u, v)   and   K

Decaps — Decapsulation

Input: sk, ct = (u, v)

1. Decrypt:
   a. m' = Compress_q(v - s^T·u, 1)
2. Reprocess:
   a. (K', r') = G(m' || H(pk))
   b. Re-run Encaps using m' and r'
   c. Compare result with received ct
3. If match: return K'
   If mismatch: return pseudorandom key derived from (sk, ct)

The reprocessing and comparison step (Fujisaki-Okamoto transform) is what makes Kyber CCA-secure. Without it, the KEM would be vulnerable to adaptive ciphertext attacks.

The Complete Flow

Alice                          Bob
  |                              |
  |--- (pk = A·s + e) --------->|  (Alice's KeyGen)
  |                              |
  |<--- (ct = (u,v), K) --------|  (Encaps using Alice's pk)
  |                              |
  |--- decrypts ct with s ------|  (Decaps: recovers K)
  |                              |
  |--- (uses K for AES/ChaCha) -|  (encrypted communication)

Important: Unlike RSA or ECDH, in Kyber the receiver generates the key pair and the sender generates the ciphertext and key. It is asymmetric in direction: encapsulation always goes from sender to receiver.

Why KEM and Not Direct Encryption?

NIST's decision to standardize KEMs instead of PKE (direct asymmetric encryption) responds to:

Simplicity: A KEM has a smaller interface and fewer failure modes.
Natural hybrid: Kyber + AES/ChaCha = hybrid encryption, which is the recommended practice even with RSA/ECC.
Manageable FO transform: The Fujisaki-Okamoto transformation from a PKE to a CCA-secure KEM is easier to analyze and verify than a direct CCA-secure PKE.

For general-purpose asymmetric encryption, HPKE (Hybrid Public Key Encryption, RFC 9180) is used, which defines how to combine a KEM with an AEAD. HPKE with Kyber is already being standardized.

References

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).

KEM StructureKEM Structure