🔒 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:

1. Alice grabs a random piece of paper (secret message K)
2. Alice creates instructions "how to send K"
3. Alice writes instructions with Bob's map (matrix A)
4. Alice adds fog to the instructions (error e₁)
5. Alice locks the instructions in a box (ciphertext C)
6. Alice sends the locked box to Bob

Bob's box opening:

1. Bob receives the locked box (ciphertext C)
2. Bob uses his secret key (s) to open it
3. Bob recovers Alice's instructions
4. Bob uses his secret location to decode them
5. 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:

---

🎮 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: Ciphertext C = (c₁, c₂)

Bob decapsulates: K' = Decapsulate(sk, C)

Result: K' = [42, 17, ...] (same as Alice's K!)

Why? Because Bob uses his secret s (from key generation) to compute the same ciphertext parts and recover K.

Answer: Bob gets K' = K (same secret as Alice generated)

---

Question 2: Why doesn't Eve just capture C and extract K herself?

Show Answer

Eve sees: Ciphertext C (encapsulated K)

Eve wants: Open box to get K

Problem: Eve doesn't have sk (Bob's secret)

Without sk, Eve can't compute what K is, even though she sees C!

Eve must solve: Given C, find encapsulated K

This is the MLWE problem: A·s + e = t (with encapsulation modifications)

Answer: Eve sees C but can't get K without Bob's sk.

---

Question 3: What makes ciphertext C different for each encapsulation? If Alice encapsulates twice, does C change?

Show Answer this.

Alice encapsulates (first time):

1. Alice generates: u₁ (random vector)
2. Alice computes: c₁₁ = Aᵀ·u₁ + e₁₁
3. Alice computes: c₂₁ = t·u₁ + e₂₁ + m₁
4. Ciphertext: C₁ = (c₁₁, c₂₁)
5. Secret: K₁

Alice encapsulates (second time):

1. Alice generates: u₂ (different random!)
2. Alice computes: c₁₂ = Aᵀ·u₂ + e₁₂ (different!)
3. Alice computes: c₂₂ = t·u₂ + e₂₂ + m₂ (different!)
4. Ciphertext: C₂ = (c₁₂, c₂₂) (different!)
5. Secret: K₂ (different!)

Answer: C changes Alice encapsulates! Each time produces different (C, K) but decapsulation still recovers K.

---

🔢 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:

1. Alice gets: pk = (A, t) from Bob
2. Alice generates: u (random vector)
3. Alice samples: e₁, e₂ (small polynomials)
4. Alice computes: m = H(u)
5. Alice computes: c₁ = Aᵀ·u + e₁, c₂ = t·u + e₂ + m
6. Alice derives: K = KDF(u, m, c₁, c₂)
7. 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!

---

🎉 What You'll Learn Next

Now you understand encapsulation! Next, we'll learn about:

🔓 Opening Boxes → Decapsulation

How Bob uses his secret key to open the box and recover the same secret!