Hidden Messages

The MLWE Problem - Intuition

---

The Simple Story

Alice wants to send a secret message to Bob.

Problem: Eve is listening to everything!

Alice's idea:

1. Multiply Bob's secret "code word" by a known "multiplier"
2. Add some "fog" (noise) to the result
3. Send the foggy message

Eve sees: A foggy message, but doesn't know if it's fogged this way or that way...

Bob knows: His secret code word! So he can "un-fog" it with his knowledge.

Eve can't: Doesn't know the secret code! Can't figure it out!

That's the core idea behind ML-KEM's security!

---

Mental Model

Hold this picture in your head:

Alice sends message:

Message = Multiplier × Secret + Fog

    ↓  
Eve sees: "123" (but doesn't know the original!)
    ↓  
Could be: 30×2 + 63 = 123
Could be: 41×3 + 0 = 123  
Could be: 60×2 + 3 = 123
    ↓  
Eve: "Which one is it?"  

Bob knows: Secret = 2
    ↓
Bob computes: (Message - Fog) ÷ Multiplier = Secret  

Think of it like:

Secret hidden in fog

Alice's idea: multiply secret by something, fog it up

Bob has the key = un-fogs it!

---

See It Happen

Let's watch Alice send a message to Bob:

---

Try It Yourself

Question 1: Alice sends "22". She tells you: "This is Multiplier × Secret + Fog". If Multiplier = 5 and Fog = 2, what's Secret?

Show Answer

Equation: 22 = 5 × Secret + 2

Bob (who knows the algorithm):

1. Subtract fog: 22 - 2 = 20
2. Divide by multiplier: 20 ÷ 5 = 4

Answer: Secret = 4

---

Question 2: Eve sees "27". She knows Multiplier = 5. What are all the possible (Secret, Fog) pairs?

Show Answer

Equation: 27 = 5 × Secret + Fog Fog = 27 - 5 × Secret

Fog must be small (let's say between -2 and 2)

Try possibilities:

• Secret = 5: Fog = 27 - 25 = 2
• Secret = 6: Fog = 27 - 30 = -3 ✗ (too negative)
• Secret = 4: Fog = 27 - 20 = 7 ✗ (too positive)

Only possibility: Secret = 5, Fog = 2

But in ML-KEM, Eve doesn't know the range of fog! So Eve would have to try:

• Secret = 0, 1, 2, 3, 4, 5, 6, ...
• For each, check if Fog is "reasonable"

That's a LOT of possibilities!

---

Question 3: If Eve doesn't know the Fog distribution, what's her challenge?

Show Answer

Eve sees "27" with Multiplier = 5

She thinks: "Is Secret = 1? Then Fog = 22" "Is Secret = 2? Then Fog = 17" "Is Secret = 3? Then Fog = 12" "Is Secret = 4? Then Fog = 7" "Is Secret = 5? Then Fog = 2" "Is Secret = 6? Then Fog = -3"

But she doesn't know: Which one is "reasonable"?

Without knowing Fog distribution, she can't eliminate any!

That's why the problem is hard!

---

The Math

The Basic LWE Equation

The Learning With Errors (LWE) problem is:

$\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{b}$

Breaking it down:

• $\mathbf{A}$ = Known matrix (multiplier)
• $\mathbf{s}$ = Secret vector (what we're hiding)
• $\mathbf{e}$ = Error vector (noise/fog)
• $\mathbf{b}$ = Observed result (what Eve sees)

In words:

Multiply matrix by secret, add error → foggy result

Why It's Hard Without Error

If $\mathbf{e} = \mathbf{0}$ (no error): $\mathbf{A}\mathbf{s} = \mathbf{b}$

This is linear algebra! We can solve: $\mathbf{s} = \mathbf{A}^{-1}\mathbf{b}$

Easy!

With $\mathbf{e}$ (with error): $\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{b}$

Now $\mathbf{e}$ is unknown too! Too many solutions!

Hard!

Module-LWE (MLWE)

MLWE uses the same equation, but with matrices of polynomials:

$\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{t}$

Where:

• $\mathbf{A} \in R_q^{k \times k}$ = Matrix of polynomials (multiplier)
• $\mathbf{s} \in R_q^k$ = Vector of polynomials (secret)
• $\mathbf{e} \in R_q^k$ = Vector of polynomials (error)
• $\mathbf{t} \in R_q^k$ = Vector of polynomials (foggy result)

Even harder! (more dimensions, more structure)

---

Why We Care

MLWE = ML-KEM's Security Foundation

ML-KEM's entire security is based on MLWE being hard!

MLWE in ML-KEM Key Generation

Bob does this during key generation:

$\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}$

Bob knows: $\mathbf{s}$ (his secret)

Eve knows: $\mathbf{A}$ and $\mathbf{t}$ (public key)

Eve wants: Find $\mathbf{s}$

Problem: Eve doesn't know $\mathbf{e}$ (the error vector!)

Result: Eve can't solve for $\mathbf{s}$ efficiently!

---

Quick Check

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

Try saying this out loud:

"Alice wants to hide a secret. She multiplies it by something, adds some 'fog' (random numbers), and sends the foggy result. Even though Eve sees the foggy result, she can't figure out the original secret because there are too many possibilities! But Bob knows the secret, so he can reverse the process."

Can you work with the LWE equation?

Try this examples:

Given: $\mathbf{A} = [3, 5]$, $\mathbf{t} = [10]$

Find: $\mathbf{s}$ and $\mathbf{e}$ such that $\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{t}$

Assume error is small (say: -2, -1, 0, 1, 2)

Try possibilities:

• $\mathbf{s} = 0$: $\mathbf{A}\mathbf{s} = 6$, so $\mathbf{e} = [10 - 6] = [4]$ ✗ (too large)
• $\mathbf{s} = 1$: $\mathbf{A}\mathbf{s} = 8$, so $\mathbf{e} = [10 - 8] = [2]$ (reasonable!)

One solution: $\mathbf{s} = [1], \mathbf{e} = [2]$

But there are many! Try others too.

---

Key Takeaways

LWE equation = $\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{b}$ Without error = Linear algebra (easy) With error = Unknown error vector (hard) Eve's problem = Too many (s, e) pairs possible Bob's advantage = Has $\mathbf{s}$ (secret) ML-KEM = Based on MLWE hardness MLWE in practice = $\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}$ with polynomial matrices

---