04 — The ML-KEM Protocol

Overview

ML-KEM has three operations. Each uses the same mathematical foundation (Module-LWE) but plays a different role.

┌─────────────┐     ┌──────────────┐     ┌──────────────┐
│   KeyGen    │────>│ Encapsulate  │────>│ Decapsulate  │
│  (Bob runs) │     │ (Alice runs) │     │ (Bob runs)   │
└─────────────┘     └──────────────┘     └──────────────┘
       │                     │                     │
       v                     v                     v
   public key            ciphertext           shared secret
   private key           shared secret

Step 1: KeyGen (Key Generation)

Who runs it: Bob (the receiver). What it produces: A public key (pk) and a private key (sk).

What Happens

1. Generate random seed: A 32-byte random value ρ.
2. Expand to matrix A: Use a hash function to generate a k×k matrix of random polynomials from ρ. Each element is a uniformly random polynomial in the ring R_q.
3. Generate secret vector s: A vector of k small polynomials (coefficients from {-η, ..., η}).
4. Generate error vector e: Another vector of k small polynomials.
5. Compute public key: t = A·s + e (polynomial matrix-vector multiplication, mod q).
6. Pack and output:
   • pk = (ρ, t) — 800 bytes (for ML-KEM-512)
   • sk = (s, pk, hash of pk) — 1,632 bytes

Why It's Secure

The public key reveals t = A·s + e. Finding s from t is exactly the LWE problem — hard even for quantum computers.

The private key s is kept secret. It's small (sparse), making it easy to store but hard to guess.

Step 2: Encapsulate

Who runs it: Alice (the sender), using Bob's public key. What it produces: A ciphertext (ct) and a shared secret (ss).

What Happens

1. Reconstruct matrix A: From the public key's ρ, regenerate the same A that Bob used.
2. Generate random vector r: A vector of k small polynomials.
3. Generate error vectors: e₁ (for the ciphertext) and e₂ (for the shared secret computation).
4. Compute u: u = Aᵀ·r + e₁
5. Compute v: v = t·r + e₂ (dot product + small error)
6. Encode message: Start with a random 32-byte message m. Encode it into a polynomial μ.
7. Compute w: w = v + μ (adding the encoded message to the noisy dot product)
8. Derive shared secret: ss = Hash(m || hash of ct)
9. Output: ct = (u, w), ss = 32-byte key

The Clever Part

Alice doesn't send the message m directly. She hides it inside the noisy polynomial dot product. Bob can recover it because he knows the secret s — an eavesdropper doesn't.

Step 3: Decapsulate

Who runs it: Bob, using his private key and the ciphertext. What it produces: The same shared secret (ss) that Alice computed.

What Happens

1. Unpack ciphertext: Extract u and w from ct.

2. Compute v': v' = s·u (using the private key s)

3. Recover message: m' = w - v' = (v + μ) - s·u

   The errors cancel out: v ≈ t·r = (A·s + e)·r ≈ A·s·r, and s·u ≈ s·A·r ≈ A·s·r. So v' ≈ v, and m' ≈ μ.

4. Decode: Convert the polynomial μ back to the 32-byte message m.

5. Re-encapsulate: Run the Encapsulate algorithm on m (with the same A and t from the public key) to get a "expected" ciphertext ct'.

6. Compare: If ct' == ct, derive ss = Hash(m || hash of ct). Otherwise, derive a random ss.

The Comparison Step (Implicit Rejection)

This is a failsafe:

• If an attacker sends a malformed ciphertext, Bob doesn't return an error.
• Instead, he returns a random-looking shared secret.
• The attacker can't tell whether decryption succeeded or failed.

This prevents chosen-ciphertext attacks — where an attacker learns information by observing how the system responds to crafted inputs.

Complete Flow Diagram

Bob                                    Alice
  |                                      |
  |-- KeyGen()                           |
  |   ρ <- random(32 bytes)              |
  |   A <- Expand(ρ)                     |
  |   s, e <- small random vectors       |
  |   t <- A·s + e                       |
  |                                      |
  |==== public key pk=(ρ,t) ============>|
  |                                      |
  |                                      |-- Encapsulate(pk)
  |                                      |   A <- Expand(ρ)
  |                                      |   r, e₁, e₂ <- small random
  |                                      |   u <- Aᵀ·r + e₁
  |                                      |   v <- t·r + e₂
  |                                      |   m <- random(32 bytes)
  |                                      |   μ <- Encode(m)
  |                                      |   w <- v + μ
  |                                      |   ct <- (u, w)
  |                                      |   ss <- Hash(m || H(ct))
  |                                      |
  |<=== ciphertext ct ==================|
  |                                      |
  |-- Decapsulate(sk, ct)                |
  |   u, w <- unpack(ct)                 |
  |   v' <- s·u                          |
  |   μ <- w - v'                        |
  |   m <- Decode(μ)                     |
  |   ct' <- Re-encapsulate(m)           |
  |   if ct' == ct:                      |
  |       ss <- Hash(m || H(ct))         |
  |   else:                              |
  |       ss <- random(32 bytes)         |
  |                                      |
  |  [Both have the same ss]             |

Key Sizes and Speed

Benchmarks on Intel Core i7 at 3.6 GHz. Times include NTT transforms.

Resources

• NIST FIPS 203 PDF — Sections 5 (KeyGen), 6 (Encapsulate), 7 (Decapsulate)
• Kyber specification: pq-crystals.org/kyber/data/kyber-specification.pdf