Putting Secrets in Boxes
Encapsulation in ML-KEM
The Simple Story
Alice wants to send a piece of paper with a secret code to Bob.
She can't just mail it (Eve reads it!). She needs a magic box!
Alice's magic box:
- Alice grabs a random piece of paper (secret message K)
- Alice creates instructions "how to send K"
- Alice writes instructions with Bob's map (matrix A)
- Alice adds fog to the instructions (error e₁)
- Alice locks the instructions in a box (ciphertext C)
- Alice sends the locked box to Bob
Bob's box opening:
- Bob receives the locked box (ciphertext C)
- Bob uses his secret key (s) to open it
- Bob recovers Alice's instructions
- Bob uses his secret location to decode them
- Bob gets the same piece of paper (K)!
Eve watches everything but:
- Eve sees Bob's map (matrix A) that was shared earlier
- Eve sees the locked box (ciphertext C) sent over network
- But Eve can't: open the box without Bob's secret key (s)!
That's how encapsulation works - Alice puts a random secret K into a locked box using the public map (A, t), Bob opens it with his secret key (s), and both have the same secret K!
Mental Model
Hold this picture in your head:
Alice's Encapsulation:
Step 1: Alice generates random secret
K = 32 random bytes
Step 2: Alice picks random message vector
u = (polynomials)
Step 3: Alice uses Bob's public map
A = matrix (shared with Alice)
Step 4: Alice computes lockbox parts
c₁ = Aᵀ·u + e₁ ← part 1
c₂ = t·u + e₂ + m ← part 2 (m from u)
Step 5: Alice locks the box
C = (c₁, c₂) ciphertext
Step 6: Alice sends box
Send C to Bob
Step 7: Both have K
Alice: K from step 1
Bob: Gets K when opening box (decapsulation)
Eve sees: A (shared earlier), C (sent)
Eve can't: Open box without s (Bob's secret!)
Think of it like:
Package shipping (Alice packs item, sends box, Bob opens)
Envelope (Write letter, seal envelope, send, Bob opens with his key)
Puzzle present (Mystery gift, wrapped, sent, opened by Bob)
See It Happen
Let's watch Alice encapsulate:
Interactive Demo: Alice Puts Secret in Magic Box
Watch as Alice encapsulates a secret key in a magic lockbox. You can change the message to encrypt and see how the encapsulation process works!
Try It Yourself
Question 1: Alice generates K = [42, 17, ...]. She encapsulates to get C = (c₁, c₂). What does Bob recover when he decapsulates?
Show Answer
Bob receives C = (c₁, c₂) and uses his secret s to compute:
K' = Decapsulation(C, s)
If the algorithm is correct, K' = K (the same secret Alice generated!)
The magic: Alice never sends K directly. She encapsulates it in a ciphertext C. Bob can recover K by decapsulating C with his secret key s.
Answer: Bob recovers exactly the same K = [42, 17, ...]
Question 2: The encapsulated ciphertext is 1088 bytes. What's broken down?
Show Answer
Ciphertext C = (c₁, c₂):
c₁: 768 bytes (256 coefficients × 12 bits × 3 polynomials / 8) c₂: 320 bytes (256 coefficients × 10 bits / 8)
Total: 1088 bytes
Answer: c₁ = 768 bytes, c₂ = 320 bytes, total = 1088 bytes
Question 3: Why does Alice need to generate random K first, then derive secret from u, m, c₁, c₂?
Show Answer
Step 1: Alice generates random K (32 bytes) - this is the shared secret she wants Step 2: Alice doesn't use that K directly in the ciphertext (too predictable!) Step 3: Alice generates random u, computes m from u Step 4: Alice computes ciphertext C from (A, t, u, e₁, e₂) Step 5: Alice re-derives shared secret as K' = KDF(u, m, c₁, c₂) Step 6: Alice uses K' (should equal K!) for symmetric encryption
Why? By re-deriving K from the same inputs Bob will use, Alice ensures she and Bob get the EXACT same shared secret!
Answer: K' should equal K if the KDF is deterministic. Both derive from same u, m, c₁, c₂!
The Math
Encapsulation Algorithm
Encapsulate(pk = (A, t)):
1. Generate random values
u ← Binomial(η₂)^k (message vector)
e₁, e₂ ← Binomial(η₂)^k (error vectors)
m ← H(encode(u)) (message from u)
2. Compute ciphertext parts
c₁ ← Aᵀ·u + e₁ (mod q)
c₂ ← tᵀ·u + e₂ + m (mod q)
3. Compress ciphertext
c ← Compress'(c₁) || Compress''(c₂)
4. Derive shared secret
K ← KDF(encode(u), encode(m), H(c))
Return (K, c)
Notation Breakdown
| Symbol | Meaning | Details |
|---|---|---|
| A | Shared matrix | Bob's matrix (3×3) |
| t | Shared vector | Bob's t = A·s + e |
| u | Alice's vector | Random (each call!) |
| e₁, e₂ | Error vectors | Small polynomials |
| m | Message | Derived from u |
| c₁, c₂ | Ciphertext | Encapsulated box |
| K | Shared secret | 32-byte symmetric key |
Compression Levels
ML-KEM compresses ciphertext parts:
| Component | Raw Size | Compression | Final Size |
|---|---|---|---|
| c₁ | 3072 bits | 10 bits/coeff | 120 bytes |
| c₂ | 3072 bits | 4 bits/coeff | 48 bytes |
| Total C | 6144 bits | - | 1088 bytes |
Trade-off: More bits = smaller C, smaller bits = decryption failures
Why We Care
Encapsulation is Random per Call
Alice generates random u each time she encapsulates:
Result: Even if she encapsulates the same K repeatedly, C changes each time!
Why? Randomness from u makes each C unpredictable.
Benefit: Attacker learning from one encapsulation doesn't help with subsequent ones.
Key Indistinguishability
Eve seeing: C = Encapsulate(pk)
Eve can't tell: Which K (of 2^256 possibilities) is in the box!
Even if Eve: Computes many encapsulations, learns nothing about future ones.
Size vs. Speed Trade-off
Ciphertext C: 1,088 bytes (fixed size)
Compared to alternatives:
- RSA: 2,048-4,096 bytes (larger!)
- ECC: 64 bytes (smaller!)
ML-KEM middle ground: Small enough (1 KB), fast enough (10-25 ms), quantum-resistant!
Quick Check
Can you explain encapsulation to a 5-year-old?
Try saying this out loud:
"Alice wants to send Bob a secret code. She puts the code in a magic lockbox by following instructions on Bob's map, then adds fog. She sends the locked box. Bob can open it with his secret key and get the same code. Eve sees the box but can't open it!"
Can you trace encapsulation?
Try this examples:
Alice encapsulates:
- Alice gets: pk = (A, t) from Bob
- Alice generates: u (random vector)
- Alice samples: e₁, e₂ (small polynomials)
- Alice computes: m = H(u)
- Alice computes: c₁ = Aᵀ·u + e₁, c₂ = t·u + e₂ + m
- Alice derives: K = KDF(u, m, c₁, c₂)
- Alice sends: C = (c₁, c₂)
Bob later decapsulates: Gets same K.
Answer: Alice encapsulates K → C, sends C, Bob opens C → K.
Key Takeaways
Encapsulation steps: Generate u, e₁, e₂, compute c₁, c₂, derive K Ciphertext: C = (c₁, c₂) compressed to 1,088 bytes Random per call: Different u each time = different C Key indistinguishable: Eve can't tell which K is in C Ciphertext size: 1,088 bytes (RSA larger, ECC smaller, ML-KEM middle ground) Bob's advantage: Has sk = s, can compute needed values Shared secret: K from Alice, K' from Bob, equals same!