⚙️ The Full Process

KEM Operations Overview

---

🎯 The Simple Story

So far we've learned:

1. Math foundations (lattices, polynomials, etc.)
2. MLWE problem (hard puzzle ML-KEM is based on)
3. Encoding (how ML-KEM stores data efficiently)
4. KEM concept (magic lockbox for shipping secrets)

Now we'll see:

How ML-KEM uses ALL these pieces together to securely send a shared secret from Alice to Bob!

The complete flow:

• Generate key pair (Alice or Bob)
• Encapsulate (put secret in box)
• Decapsulate (open box to get secret)
• Use secret for symmetric encryption

---

🧠 Mental Model

Hold this picture in your head:

Complete ML-KEM Flow:

PHASE 1: Key Generation (once, by Bob)
 ┌─────────────────────────────────────┐
 │  Bob creates matrix A (seed)      │
 │  Bob picks secret: s              │
 │  Bob adds noise: e                │
 │                                     │
 │  Compute: t = A·s + e              │
 │                                     │
 │  Public key: (A, t)               │
 │  Private key: s                   │
 └─────────────────────────────────────┘
            ↓
         Bob shares (A, t) with Alice
            ↓
       
PHASE 2: Encapsulation (Alice sends secret)
 ┌─────────────────────────────────────┐
 │  Alice has Bob's (A, t)             │
 │  Alice generates random message: u │
 │  Alice adds noise: e₁               │
 │                                     │
 │  Compute: c₁ = Aᵀ·u + e₁            │
 │           c₂ = tᵀ·u + e₂ + m      │
 │                                     │
 │  Ciphertext: (c₁, c₂)              │
 │  Shared secret: K (from u, m, c)    │
 └─────────────────────────────────────┘
            ↓
         Alice sends (c₁, c₂) to Bob
            ↓
       
PHASE 3: Decapsulation (Bob opens box)
 ┌─────────────────────────────────────┐
 │  Bob has: s (private)               │
 │         (c₁, c₂) (ciphertext)        │
 │                                     │
 │  Bob computes: Decrypt using s     │
 │  Bob recovers: message m           │
 │  Bob derives: same K'               │
 └─────────────────────────────────────┘
            ↓
         Now both have K!
            ↓
       
PHASE 4: Symmetric Encryption
 ┌─────────────────────────────────────┐
 │  Alice uses K: Encrypt(M)          │
 │  Bob uses K: Decrypt(Cipher)        │
 │                                     │
 │  Result: Both can talk privately!   │
 └─────────────────────────────────────┘

Key idea: KEM ships K securely, symmetric does the work!

---

📊 See It Happen

Let's watch the complete sequence:

---

🎮 Try It Yourself

Question 1: What's the difference between public key encryption and KEM + symmetric?

Show Answer

Public key encryption:

• Alice encrypts message directly with Bob's pk
• Ciphertext = Encrypted(message)

KEM + symmetric:

• Alice encapsulates: (K, C) = Encapsulate(pk)
• Alice uses K: Encrypted = SymmetricEncrypt(message, K)
• Alice sends: C, Encrypted
• Bob gets: K' = Decapsulate(sk, C)
• Bob decrypts: Message = SymmetricDecrypt(Encrypted, K')

KEM + symmetric: Separate secure key shipping from encryption, much faster!

Answer: KEM sends K, then symmetric (AES-GCM) uses K for encryption.

---

Question 2: If Alice generates K, why can't Eve just sniff the network to get K?

Show Answer

Eve sees: Ciphertext C (the locked box)

Eve knows: C = Encapsulate(pk, K) → Where K is random secret

Eve wants: Open box → get K

Problem: Eve doesn't have sk to open the box!

Eve tries: Find K from C alone But that's exactly the MLWE problem (hard!)

Result: Eve can't get K without sk. She must solve MLWE = believed impossible!

Answer: Eve sees C, not K. She can't open box without sk.

---

Question 3: Why does Bob need to decapsulate? Why not just receive K directly?

Show Answer

If Alice sent K directly (in cleartext), Eve would see K!

Bob would get: K (but so would Eve!)

Problem: K would be known to Eve = useless for encryption!

Solution: Alice encapsulates K into C, sends C instead

Bob opens box: C → K' (recovered securely from C)

Eve sees C, but can't open → doesn't get K

Answer: Encapsulation hides K in ciphertext C, Eve can't open without sk.

---

🔢 The Math

Complete ML-KEM Algorithm

1. Key Generation:

KeyGenerate():
  1. A ← sample matrix (polynomials)
  2. s ← sample vector (secret)
  3. e ← sample vector (error, small!)
  4. t ← A·s + e (mod q)
  
  Return (pk = (A, t), sk = s)

2. Encapsulation:

Encapsulate(pk = (A, t)):
  1. u ← sample vector (polynomial)
  2. e₁ ← sample vector (error, small!)
  3. m ← H(u) (message)
  4. c₁ ← Aᵀ·u + e₁ (ciphertext part 1)
  5. c₂ ← tᵀ·u + e₂ + m (ciphertext part 2)
  6. C ← (c₁, c₂) (ciphertext)
  7. K ← KDF(u, m, C) (shared secret)
  
  Return (K, C)

3. Decapsulation:

Decapsulate(sk = s, C = (c₁, c₂)):
  1. Decompress: c₁, c₂
  2. Recover: m' = c₂ - tᵀ·c₁ - c₁ᵀ·s
  3. Check: m' is reasonable?
  4. If yes: u' = compute(m')
       else: u' = implicit rejection
  5. Derive K' = KDF(u', m', C)
  
  Return K'

Operation Timing (ML-KEM768)

Operation	Time	What Happens
Key Generation	5 to 15 ms	Generate A, s, e, compute t
Encapsulation	10 to 25 ms	Sample, compute c1, c2, derive K
Decapsulation	10 to 25 ms	Decompress, recover m, derive K prime
Symmetric encrypt	Less than 1 ms	AES-GCM on data using K

---

💡 Why We Care

KEM + Symmetric Pattern

Separate concerns:

1. KEM = Securely ship key K (small, fast)
2. Symmetric = Encrypt/decrypt data with K (tiny, very fast)

Benefits:

• KEM: 1,088 bytes ciphertext (fixed size)
• Symmetric: Same size as input (plus tag)

Total overhead: 1,088 bytes (key shipping) + small symmetric tag

Speed: Key shipping (10-25 ms) + symmetric (sub-ms) = ~25 ms total

ML-KEM Security Layers

Combined: KEM sends K securely, symmetric uses K for message encryption

---

✅ Quick Check

Can you explain the complete KEM flow to a 5-year-old?

Try saying this out loud:

"Alice wants to send a secret key to Bob safely. Bob creates a lockbox and special key. Alice puts the secret key in the box and closes it. She sends the box to Bob. Bob opens it with his special key. Now both have the same secret key to talk privately!"

Can you trace the complete sequence?

Try this examples:

Alice and Bob exchange:

1. Bob generates: (pk, sk) → shares pk with Alice
2. Alice generates: random u, e₁
3. Alice computes: c₁ = Aᵀ·u + e₁, c₂ = tᵀ·u + e₂ + m
4. Alice sends: C = (c₁, c₂) to Bob
5. Bob has: sk = s
6. Bob recovers: m from C using s
7. Bob derives: K' from m
8. Result: K' = K (shared secret!)

Then both use K for symmetric encryption.

Answer: KEM ships K securely, symmetric uses K for secure messaging.

---

🎓 Key Takeaways

✅ KEM operations: KeyGen, Encapsulate, Decapsulate ✅ KeyGen: Create pk = (A, t), sk = s from matrix A, secret s, error e ✅ Encapsulate: Put K in box C (c₁, c₂ derivation from A, t, plus errors) ✅ Decapsulate: Open box C → recover K' using sk ✅ Symmetric: Use K for AES-GCM encryption/decryption ✅ Total security: KEM sends K, symmetric uses K ✅ Pattern: Separate concerns = faster, smaller, more secure

---

🎬 Complete Tutorial Overview!

You've now learned everything to understand how ML-KEM works:

Phase	What You Learned	Mental Model
Math Foundations	Lattices, polynomials, matrices	Maps, recipes, instruction grids
MLWE Problem	Hard puzzle ML-KEM uses	Foggy maps, hidden messages
Encoding	How ML-KEM stores data	Shrinking rooms, magic seeds
KEM Concept	How key encapsulation works	Magic lockboxes
Operations	How ML-KEM's algorithms work	Complete process flow

Next: Dive into the algorithm细节 with the detailed chapters!

---

🎉 Ready to Dive Deeper?

Now you understand the big picture! To learn the algorithms in detail, continue with:

🔑 Making the Key → Key Generation

How Bob generates public/private key pairs based on MLWE!

Or jump to:

• 🔒 Putting Secrets in Boxes → Encapsulation
• 🔓 Opening Boxes → Decapsulation
• 💻 Practical Implementation → Code Examples