Skip to main content

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:

A∈Rqk×k\mathbf{A} \in R_q^{k \times k}

Where:

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

Total: 9×256=2,3049 \times 256 = 2,304 coefficients

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

Raw size: 2,304×12=27,6482,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 SS
  2. Bob uses PRG: Expand SS → Matrix A\mathbf{A}
  3. Bob stores: Just SS (not A\mathbf{A}!)
  4. When needed: Re-expand SS → A\mathbf{A} (deterministic)

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

Deterministic Expansion​

Given seed SS, PRG computes:

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

PRG:{0,1}256→Zqn×n\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