🔑 Making the Key
Key Generation in ML-KEM
🎯 The Simple Story
Bob wants to receive secret messages from Alice.
He needs: A locked box (public key) that anyone can close + a special key (private key) only he can open.
Bob creates his lockbox like this:
- Bob creates a grid of instructions: Matrix A (from a tiny 32-byte seed)
- Bob picks a secret location: Secret s (small random coefficients)
- Bob adds fog: Error vectors e (small random coefficients)
- Bob marks the foggy location: Computes t = A·s + e
- Bob shares: Sends grid + foggy location (public key = A, t)
- Bob keeps: His secret location hidden (private key = s)
Eve sees: The grid (A) and the foggy location (t), but doesn't know which dot is Bob's secret!
Bob knows: His secret location (private key = s)
That's how ML-KEM generates keys - Bob creates a "foggy map" (public key) but keeps the "true location" (private key) secret!
🧠 Mental Model
Hold this picture in your head:
Bob's Key Generation:
Step 1: Bob creates matrix A
Public: 32-byte seed → PRG → matrix A (3×3 polynomials)
Step 2: Bob picks secret s
Secret: Small polynomials (coefficients -2 to 2)
Step 3: Bob adds error e
Error: Small polynomials (coefficients -2 to 2)
Step 4: Bob computes t
Compute: t = A*s + e (with mod 3329)
Step 5: Bob shares public key
Public key: (A, t) = 1,184 bytes
Private key: s = 64 bytes (kept secret!)
Think of it like:
🗺️ Scavenger hunt (Bob draws map, hides treasure, sends foggy map)
📦 Lockbox (Bob makes box anyone can close, but only he can open)
🎭 Disguise (Bob publishes puzzle, only he knows solution)
📊 See It Happen
Let's watch Bob generate keys:
🎮 Try It Yourself
Question 1: Bob creates matrix A with 3 polynomials (9 total). Each has 256 coefficients. What's the raw size if each is 12 bits?
Show Answer
Total coefficients: 3 × 256 = 768 coefficients
Raw bits: 768 × 12 = 9,216 bits
Raw bytes: 9,216 ÷ 8 = 1,152 bytes
Answer: 1,152 bytes raw (but compressed to 1,184 bytes in pk!)
Question 2: Bob's secret s is small coefficients −2 to +2. Why does Eve seeing (A, t) make it hard to find s?
Show Answer
Eve sees: Matrix A and vector t
Eve wants: Find secret s
Problem: Eve doesn't know error e!
Eve must solve: A·s + e = t
Two unknowns: s and e!
Eve can try: For every s, compute what e should be to match t
But s has: 5^256 possibilities (each coeff −2 to +2, 256 coeffs)
That's ~10^178 possibilities - more atoms than universe!
Answer: Too many (s, e) pairs possible, Eve can't find the true one!
Question 3: Why is Bob's secret s small coefficients (−2 to +2)? What if they were 0 to 3328 (full range)?
Show Answer this.
If s had full range (0 to 3328), Eve could still search all possibilities.
But Bob's advantage: He knows s exactly!
Bob's use case: He needs to decode during decapsulation
If s were huge, adding error e would sometimes cause failures (Bob can't recover correctly!)
Small s plus small e equals Bob can subtract A·s from t to find e, then recover message!
Answer: Small s equals Bob can use it for decoding, Eve still can't find it.
🔢 The Math
Key Generation Algorithm
KeyGenerate():
1. Sample matrix A from seed
seed generates (using pseudo-random generator)
matrix A is a polynomial matrix in ring R_q
2. Sample secret vectors
s from Binomial(eta1)^k (small polynomials)
Each coefficient in set negative 2, 1, 0, 1, or 2
256 coefficients per polynomial, 3 polynomials total
3. Sample error vectors
e from Binomial(eta1)^k (small polynomials)
Each coefficient in negative 2, 1, 0, 1, or 2
256 coefficients per polynomial, 3 polynomials total
4. Compute public component
t = A*s + e (mod 3329)
Multiply matrix by vector in polynomial ring
5. Output keys
pk = (A, t) encoded as public key (1,184 bytes)
sk = s encoded as private key (64 bytes)
Return (pk, sk)
Parameter Values (ML-KEM768)
| Symbol | Value | Meaning |
|---|---|---|
| n | 256 | Polynomial degree |
| q | 3329 | Coefficient modulus |
| k | 3 | Matrix size = 3x3 |
| eta1 | 2 | Key generation error parameter |
| pk size | 1,184 bytes | A (864) plus t (320) |
| sk size | 64 bytes | s (encoded) |
Matrix Expansion in Detail
Given 32-byte seed S:
- Initialize PRG (pseudo-random generator) with seed S
- Generate 9 polynomials (each 256 coefficients)
- For each coefficient: Sample from uniform distribution mod 3329
- This creates matrix A in polynomial ring R_q
Total matrix size: 9 × 256 = 2,304 coefficients
Storage: Seed S is only 32 bytes (expand when needed!)
💡 Why We Care
Security: MLWE Hardness
Eve's problem: Given (A, t), find s
This is exactly MLWE: matrix multiplication plus unknown e is the hard puzzle!
Without e: Eve could solve using s = A^(-1)*t (easy linear algebra)
With e: Eve must find (s, e) from one equation, two unknowns (too hard!)
Complexity: about 2^256 operations (256-bit security)
Bob's Advantage
Bob knows: s (he chose it)
When encrypting: Alice encapsulates using A and t
When decrypting: Bob computes: e = t - A*s
Bob can subtract out the noise Eve added!
Key Sizes
| Component | Raw Size | Encoded Size |
|---|---|---|
| Matrix A | 3,456 bytes | 864 bytes |
| Vector t | 1,152 bytes | 320 bytes |
| Public key pk | 4,608 bytes | 1,184 bytes |
| Private key sk | - | 64 bytes |
Compression ratio: About 96% smaller (1,184 vs. 4,608 bytes)
✅ Quick Check
Can you explain key generation to a 5-year-old?
Try saying this out loud:
"Bob wants to receive secret messages. He draws a grid, picks a secret spot, adds fog, marks the foggy location, and shares the grid plus mark. He keeps the real secret. The foggy mark is the public key, the secret spot is the private key!"
Can you work through key generation?
Try this examples:
Bob generates keys:
- Bob generates: 32-byte seed S
- Bob expands S → matrix A (9 polynomials)
- Bob samples: s = small random polynomials
- Bob samples: e = small random polynomials
- Bob computes: t = A*s + e (mod 3329)
- Output: pk = (A, t), sk = s
Answer: pk is public (shared), sk is secret (Bob keeps hidden).
📋 Key Takeaways
✅ KeyGen steps: Sample A (seed), sample s/e, compute t, encode ✅ Public key: pk = (A, t) = 1,184 bytes (shared openly) ✅ Private key: sk = s = 64 bytes (kept secret!) ✅ Security: MLWE hardness: A*s + e = t (two unknowns!) ✅ Bob's advantage: Has s (knows e when needed) ✅ Key sizes: pk 1,184 bytes, sk 64 bytes (compressed) ✅ Matrix generation: 32-byte seed → 3,456 bytes (PRG expansion)
🎉 What You'll Learn Next
Now you understand key generation! Next, we'll learn about:
🔒 Putting Secrets in Boxes → Encapsulation
How Alice encapsulates a random secret into ciphertext to send to Bob!