Opening Boxes

Decapsulation in ML-KEM

---

The Simple Story

Bob received a locked box from Alice.

Inside the box is a piece of paper with the secret code Alice sent, but Bob can't read it yet.

Bob's special key (s) can open the box:

1. Bob takes the locked box (ciphertext C)
2. Bob uses his secret key (s) to unlock it
3. Bob "subtracts out" the fog Alice added
4. Bob finds the piece of paper inside (message m)
5. Bob does the same math Alice did to get the same secret (K)

Eve's problem: Eve sees the locked box (C) but doesn't have Bob's special key (s)!

Result: Bob recovers the secret K, Eve can't!

Why it works: Bob knows where Alice started (his secret), so he can unwind exactly what Alice did!

---

Mental Model

Hold this picture in your head:

Bob's Decapsulation:

Step 1: Bob receives ciphertext
    C = (c₁, c₂) from Alice
    
Step 2: Bob decompresses
    c₁' = Decompress(c₁)
    c₂' = Decompress(c₂)
    
Step 3: Bob computes message recovery
    m' = c₂' - tᵀ·c₁' - c₁'ᵀ·s
    Where s is Bob's secret!
    
Step 4: Bob checks message
    Is m' reasonable (small coefficients)?
    
    If yes: Compute u' = recovery function(m')
    If no:  Use implicit rejection
    
Step 5: Bob derives secret
    K' = KDF(u', m', c₁', c₂')
    
Result: K' = K (same secret as Alice!)

Think of it like:

Mailbox (Find mail in locked box with your key)

Reading (Decode what was written by following instructions)

Reversing (Bob knows where Alice started, can backtrack)

---

See It Happen

Let's watch Bob decapsulate:

---

Try It Yourself

Question 1: Alice encapsulated K = [7, 22, ...] into C = (c₁, c₂). Bob has s from key generation. What does Bob compute for m'?

Show Answer

Bob computes message recovery:

m' = c₂ - tᵀ·c₁ - c₁ᵀ·s

Where:

• c₂ = from ciphertext (Alice's part 2)
• t = Bob's t from key generation
• c₁ = from ciphertext (Alice's part 1)
• s = Bob's secret (from key generation)

Bob knows: s (keeps secret during key gen)

Bob computes: Result m' (same as Alice's m!)

Answer: m' = m (Bob can recover Alice's message)

---

Question 2: Why can Bob compute m' when Eve can't? What's Bob's advantage?

Show Answer

Both Bob and Eve see:

• A, t (shared in public key)
• C = (c₁, c₂) (ciphertext)

Bob advantage: Has s (secret from key generation)

Bob computes: m' = c₂ - tᵀ·c₁ - c₁ᵀ·s

Bob knows s, so can solve!

Eve sees: Same c₁, c₂, A, t

But Eve doesn't know s, so can't compute the same thing.

She must: Find s AND e from the equation (impossible!)

Answer: Bob has s (knows secret), Eve doesn't!

---

Question 3: What if m' is "invalid" (coefficients not in range)? What does Bob do?

Show Answer this.

Bob checks: Is m' bounded (close to 0)?

If m' is reasonable (coeffs ≈ small), Bob continues:

• Bob recovers: u' (from m')
• Bob derives: K' (from u', m', C)

If m' is invalid (coeffs too big), Bob doesn't know if:

• Alice truly made bad message
• Attacker modified ciphertext
• Decryption error

Solution: Implicit rejection

• Bob still computes: K' (but from H(C) instead)
• Attacker can't tell: Bob succeeded or failed!

Answer: Bob uses same K either way (implicit rejection).

---

The Math

Decapsulation Algorithm

Decapsulate(sk = s, C = (c₁, c₂)):
  1. Decompress ciphertext
     c₁' = Decompress(c₁, d₁)
     c₂' = Decompress(c₂, d₂)
  
  2. Attempt message recovery
     m' = c₂' - tᵀ·c₁' - c₁'ᵀ·s
  
  3. Verify message bounds
     If m' is "reasonable" then
        u' = compute(m')
     Else
        u' = implicit_rejection
  
  4. Derive shared secret
     K' = KDF(u', m', c₁', c₂')
     or
     K' = KDF(H(c₁', c₂'), 0³², H(c₁', c₂'))
  
  Return K'

Message Recovery Derivation

Alice computes: $c₁ = Aᵀ u + e₁$ $c₂ = tᵀ u + e₂ + m$

Bob knows: $t = A s + e$

Bob computes message recovery: $m' = c₂ - tᵀ c₁ - c₁ᵀ s$

Expanding (with algebra): $= (tᵀ u + e₂ + m) - (A s + e)ᵀ c₁ - c₁ᵀ s$ $= tᵀ u + e₂ + m - sᵀ Aᵀ c₁ - eᵀ c₁ - c₁ᵀ s$ $= tᵀ u + e₂ + m - tᵀ c₁ - eᵀ c₁ - sᵀ e₁$ $= e₂ + m - eᵀ c₁ - sᵀ e₁$ $= m - (eᵀ c₁ - sᵀ e₁ - e₂)$

Where the error terms cancel out (they're small!)

Result: $m' ≈ m$ (recover Alice's message)

Implicit Rejection

If Bob can't recover valid m, he uses implicit rejection:

$K' = KDF(H(c₁ || c₂), \text{0}³², H(c₁ || c₂))$

Where 0³² = 32 bytes of zeros.

Property: Attacker can't distinguish between:

• Bob successfully decapsulating
• Bob failing decapsulation

So attacker doesn't learn if modified ciphertext!

---

Why We Care

Decryption Failure Probability

When Bob computes m', error terms accumulate:

$e_2 + e^T c_1 - s^T e_1$

All terms are small polynomials:

• $e_2$ sampled from Binomial(η₂)
• $e^T c_1$ and $s^T e_1$ are small (multiplication results small + small)

Probability of too large: ~2^-139

Meaning: One in 10^42 decapsulations fail. Basically never!

Bob's Decryption Advantage

Bob knows: s (his secret from key generation)

Eve doesn't: s (only sees A, t, C)

Result:

• Bob can: Compute the subtraction (cancel errors)
• Eve can't: Doesn't know s to cancel with

Security Property

If Bob implicitly rejects (can't recover m):

Eve can't tell if:

• Alice sent bad message
• Someone modified ciphertext
• Bob's error terms too big

Benefit: Attacker learns nothing from failed attempts!

---

Quick Check

Can you explain decapsulation to a 5-year-old?

Try saying this out loud:

"Bob gets a locked box from Alice. He uses his secret key to open it. Inside is a paper with instructions. Bob follows them backward to find what Alice wrote. He gets the same secret number Alice put in the box!"

Can you trace decapsulation?

Try this examples:

Bob decapsulates:

1. Bob receives: C = (c₁, c₂)
2. Bob decompresses: c₁', c₂'
3. Bob computes: m' = c₂' - tᵀ·c₁' - c₁'ᵀ·s
4. Bob checks: Is m' bounded?
5. If yes: Compute u' = f(m')
6. Bob derives: K' = KDF(u', m', c₁', c₂')
7. Result: K' = K (same secret Alice sent)

Answer: Bob uses s (secret) to recover K, Eve can't!

---

Key Takeaways

Decapsulation steps: Decompress C, recover m', derive K' Bob's advantage: Has s (can cancel error terms) Message recovery: m' = c₂ - tᵀ·c₁ - c₁ᵀ·s Error cancellation: Errors are small, can still decode Failure probability: ~2^-139 (basically never fails) Implicit rejection: If fails, can't tell (attacker learns nothing) Shared secret: K' = K (Bob gets same secret!)

---