🔮 The Magic Seed

How ML-KEM Shrinks 3,456 Bytes to 32

---

🎯 The Simple Story

Imagine you need to send someone the entire city of New York:

Problem: It's too big!

Solution: Send them a magic seed instead!

You tell them: "Plant this seed and you'll get the whole city!"

When they "plant" it (run a program), New York grows out of that one tiny seed!

That's how ML-KEM sends huge matrices as just 32 bytes - like sending a seed instead of the entire city!

---

🧠 Mental Model

Hold this picture in your head:

Normal way (impossible):

Full Matrix A:
  ┌─────────────────┐
  │ 256 coeffs      │ × 9 polynomials
  │ (2,304 total)   │ = 3,456 bytes raw!
  │                 │ Too big to send!
  └─────────────────┘
    ↓ ↓ ↓ ↓ ↓ ↓ ↓
Sender toReceiver: [3,456 bytes]
    Too slow!

Better way (magic):

1. Bob picks random 32-byte seed
2. Expands seed → generates entire matrix
3. Stores seed, not matrix!

Sender toReceiver: [32 bytes] ← Just the seed!
    Instant!

Receiver re-expands → same matrix Bob created!

Think of it like:

🌱 Plant a tree (seed → full tree)

📚 Read a book (index → full story)

🔑 Recipe card (list of steps → full meal)

ML-KEM: Seed → Expand → 3,456 bytes (deterministic!)

---

📊 See It Happen

Let's watch the magic seed process:

---

🎮 Try It Yourself

Question 1: Matrix A = 9 polynomials × 256 coefficients = 2,304 coefficients × 12 bits each = 27,648 bits. How many bytes raw?

Show Answer

Total bits: 2,304 × 12 = 27,648 bits

Convert to bytes: 27,648 ÷ 8 = 3,456 bytes

Answer: 3,456 bytes raw

---

Question 2: If we use the seed compression trick, how many bytes do we send instead?

Show Answer

Traditional: Send 3,456 bytes directly

Seed trick: Send just 32-byte seed

Compression ratio: 3,456 ÷ 32 = 108× smaller!

Answer: 32 bytes (99% smaller!)

---

Question 3: Why is this better than sending the raw matrix? Speed?

Show Answer

Assume 1 second to send 1 kilobyte:

Raw: 3,456 bytes × 1 sec/KB = ~3.5 seconds Seed: 32 bytes × 1 sec/KB = ~0.03 seconds (instant!)

Speedup: 100× faster transmission (like 3 seconds vs 0.03 seconds)

Answer: 100× faster to send seed vs raw matrix!

---

🔢 The Math

Problem: Huge Matrices

In ML-KEM, matrix A has:

$\mathbf{A} \in R_q^{k \times k}$

Where:

• $k = 3$ for ML-KEM768
• $k \times k = 9$ polynomial entries
• Each polynomial has 256 coefficients

Total: $9 \times 256 = 2,304$ coefficients

Each coefficient: 12 bits (0 to 3,328)

Raw size: $2,304 \times 12 = 27,648$ bits = 3,456 bytes

Sending 3,456 bytes = Too slow!

Solution: Pseudo-Random Generator (PRG)

Idea: Store a small seed, expand when needed!

1. Bob generates: 32-byte random seed $S$
2. Bob uses PRG: Expand $S$ → Matrix $\mathbf{A}$
3. Bob stores: Just $S$ (not $\mathbf{A}$!)
4. When needed: Re-expand $S$ → $\mathbf{A}$ (deterministic)

PRG property: Same seed → same output (always!)

Deterministic Expansion

Given seed $S$, PRG computes:

$\mathbf{A} = \text{PRG}(S)$

$\text{PRG}: \{0, 1\}^{256} \rightarrow \mathbb{Z}_q^{n \times n}$

Maps 256-bit seed to 3,456-byte matrix deterministically!

---

💡 Why We Care

Transmission Speed

Without seed:

• Send 3,456 bytes = 3.4 KB
• At 1 KB/s: ~3.5 seconds

With seed:

• Send 32 bytes = 0.03 KB
• At 1 KB/s: ~0.03 seconds

100× faster!

Storage Efficiency

Public key contains:

• Matrix expansion (3,456 → 864 bytes)
• Vector t (1,152 → 320 bytes)

Total: 1,184 bytes (still much smaller than 4.6 KB!)

Security Property

The seed approach doesn't just shrink size—it's essential for ML-KEM:

• Attacker sees: 32-byte seed
• Can re-expand: To get matrix A
• But matrix A is: Deterministically generated
• Security: Based on seed hardness + MLWE hardness

Seed just tells you HOW to recompute A, doesn't give you A itself!

---

✅ Quick Check

Can you explain the seed trick to a 5-year-old?

Try saying this out loud:

"The seed trick is like storing a recipe card instead of the entire meal. When you want the meal, you just follow the recipe. ML-KEM sends a tiny seed, and the receiver expands it to get the whole matrix!"

Can you compute seed compression?

Try this examples:

Matrix has 2,304 coefficients × 12 bits = 27,648 bits

Send raw: 27,648 ÷ 8 = 3,456 bytes Send seed: 32 bytes

Compression ratio: 3,456 ÷ 32 = 108×

Speedup: Sending takes 100× less time!

---

🎓 Key Takeaways

✅ Seed trick = Store 32 bytes, expand to 3,456 bytes ✅ PRG = Pseudo-random generator (deterministic) ✅ Compression = 108× smaller, 100× faster ✅ Re-expand = Same seed → same matrix (always!) ✅ Public key = Seed + vector t (1,184 bytes total) ✅ Security still fine = Seed hardness + MLWE hardness

---

🎉 What You'll Learn Next

Now you understand encoding and the seed trick! Next, we'll understand key generation:

🔑 Making the Key → Key Generation

How ML-KEM生成 (generates) public/private key pairs!