The MLWE Equation

The Official Problem Statement

---

The Simple Story

Here's the formal problem statement (in plain terms!):

Given:

• A multiplication table (matrix $\mathbf{A}$)
• A result vector ($\mathbf{t}$)

Find:

• A secret vector ($\mathbf{s}$)
• An error vector ($\mathbf{e}$)

Such that: $\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{t}$

Where:

• $\mathbf{s} = \text{Bob's secret (what we're hiding)}$
• $\mathbf{e} = \text{Random fog (confuses Eve)}$
• $\mathbf{t} = \text{Fogged result (what Eve sees)}$

Problem: Two unknowns ($\mathbf{s}$ and $\mathbf{e}$), one equation! Too many solutions!

Secret: Choose just one pair ($\mathbf{s}$, $\mathbf{e}$) that produces $\mathbf{t}$. That's the MLWE problem.

---

Mental Model

Hold this picture in your head:

The MLWE Problem:

Given:
  ┌───┬───┬───┐
  │ A │ B │ C │ ← Matrix 𝐀
  ├───┼───┼───┤
  │ D │ E │ F │
  ├───┼───┼───┤
  │ G │ H │ I │
  └───┴───┴───┘

And vector:
  ┌───┐
  │ J │ ← Vector 𝐭
  └───┘

Find:
  ┌───┐
  │ s │ ← Vector 𝐬 (secret)
  ├───┤
  │ e │ ← Vector 𝐞 (error)
  └───┘ 

Such that:
  𝐀·𝐬 + 𝐞 = 𝐭

In other words:

What secret $\mathbf{s}$ and error $\mathbf{e}$ multiply with $\mathbf{A}$ to produce $\mathbf{t}$?

This is exactly "Finding the Closest Point on a Lattice"! (SVP - Shortest Vector Problem)

---

See It Happen

Let's see what Eve and Bob do:

---

Try It Yourself

Question 1: Given $\mathbf{A} = [3, 5]$, $\mathbf{t} = [10]$, find all ($\mathbf{s}$, $\mathbf{e}$) pairs such that $\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{t}$

Show Answer

Equation: $3s + e = 10$

Try different values:

$s$	$e = 10 - 3s$	Reasonable?
0	10	✗ Too large
1	7	✗ Too large
2	4	✗ Too large
3	1	Reasonable!
4	-2	Reasonable!

But we don't know what "reasonable" means! Could be ($s$, $e$) = (5, -5), (6, -8), etc.

Many possibilities!

---

Question 2: If error must be between -2 and +2, which values of $s$ work with $\mathbf{A} = [3]$, $\mathbf{t} = [10]$?

Show Answer

Equation: $3s + e = 10$

Error $e \in [-2, -1, 0, 1, 2]$

Try each:

• $e = -2$: $3s = 12 \rightarrow s = 4$
• $e = -1$: $3s = 11 \rightarrow s = 3.67$ ✗ (not integer)
• $e = 0$: $3s = 10 \rightarrow s = 3.33$ ✗ (not integer)
• $e = +1$: $3s = 9 \rightarrow s = 3$
• $e = +2$: $3s = 8 \rightarrow s = 2.67$ ✗ (not integer)

Valid solutions: ($s=4$, $e=-2$) or ($s=3$, $e=+1$)

Which one is the "true" secret? We don't know!

---

Question 3: Why does this become much harder with multiple equations? (ML-KEM has $k=3$ equations)

Show Answer

With 3 equations:

$$\begin{bmatrix} A_{11} & A_{12} & A_{13} \\ A_{21} & A_{22} & A_{23} \\ A_{31} & A_{32} & A_{33} \end{bmatrix} \begin{bmatrix} s_0 \\ s_1 \\ s_2 \end{bmatrix} + \begin{bmatrix} e_0 \\ e_1 \\ e_2 \end{bmatrix} = \begin{bmatrix} t_0 \\ t_1 \\ t_2 \end{bmatrix}$$

Now we must find:

• $\mathbf{s} = (s_0, s_1, s_2)$ - 3 unknowns
• $\mathbf{e} = (e_0, e_1, e_2)$ - 3 unknowns

Total: 6 unknowns! But we still only know $\mathbf{A}$ and $\mathbf{t}$!

Each unknown can take ~5 possible values (error -2 to +2)

Total possibilities: ~5^6 = 15,625

Much harder! (In real ML-KEM: 5^256 ≈ 10^178)

---

The Math

MLWE Problem Statement

Module-Learning With Errors (MLWE): Given $\mathbf{A} \in R_q^{k \times k}$ and $\mathbf{t} \in R_q^k$, find $\mathbf{s}, \mathbf{e} \in R_q^k$ such that:

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

Where:

• $R_q = \mathbb{Z}_q[x]/(x^{256} + 1)$ (polynomial ring, coefficients 0 to 3328)
• $k = 3$ for ML-KEM768 (matrix size)
• $\mathbf{s} \leftarrow \chi_{\eta_1}^k$ (secret from small error distribution)
• $\mathbf{e} \leftarrow \chi_{\eta_2}^k$ (error from small error distribution)

In words:

Find a polynomial vector $\mathbf{s}$ that, when multiplied by matrix $\mathbf{A}$, and added to a small error polynomial vector $\mathbf{e}$, produces result $\mathbf{t}$

Security Reduction

The beauty of MLWE is its security reduction to SVP:

Theorem: If you can solve MLWE efficiently → You can solve SVP → Break lattice problems

Since SVP has no known efficient algorithm (40+ years of research), MLWE is believed hard!

Quantum resistance: No known quantum algorithm better than Grover's speedup (square root)

MLWE Parameters (ML-KEM768)

Parameter	Symbol	Value	Meaning
Polynomial degree	$n$	256	Each polynomial: 256 coefficients
Coefficient modulus	$q$	3329	Coefficients: 0 to 3328
Matrix size	$k$	3	Matrix: 3×3 = 9 polynomials
Error param 1	$\eta_1$	2	Key generation error (-2 to +2)
Error param 2	$\eta_2$	2	Encapsulation error (-2 to +2)

Result:

• Each entry = polynomial with 256 coefficients
• Matrix $\mathbf{A}$ = 9 polynomials = 2,304 coefficients total
• Each coefficient values: 0, 1, 2, ..., 3328

Total possibilities:

• Each coefficient: 3,329 values
• Matrix: 3,329^2,304 ≈ 10^10,000 astronomically large!
• Even with error distribution: Still huge search space!

---

Why We Care

MLWE in ML-KEM Key Generation

Bob's key generation algorithm:

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

Alice receives: $(\mathbf{A}, \mathbf{t})$ (public key)

Alice's encapsulation:

• Uses $\mathbf{A}$ and $\mathbf{t}$
• Derives shared secret
• Sends ciphertext $(\mathbf{c}_1, \mathbf{c}_2)$

Bob's decapsulation:

• Has $\mathbf{s}$ (private key)
• Can recover $\mathbf{e}$ from $\mathbf{t}$
• Derives same shared secret!

Eve's problem: Find $\mathbf{s}$ given $(\mathbf{A}, \mathbf{t})$ → Equivalent to MLWE → Hard!

MLWE vs LWE

LWE (Learning With Errors): $\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{b}$

With:

• $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$ (regular matrix)
• $\mathbf{s} \in \mathbb{Z}_q^n$ (vector of integers)
• $\mathbf{e} \in \mathbb{Z}_q^m$ (error vector)

MLWE (Module-LWE): $\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{t}$

With:

• $\mathbf{A} \in R_q^{k \times k}$ (matrix of polynomials)
• $\mathbf{s} \in R_q^k$ (vector of polynomials)
• $\mathbf{e} \in R_q^k$ (error of polynomials)

Why MLWE: Faster operations, smaller keys, NTT enabled!

---

Quick Check

Can you state the MLWE problem?

Try saying this out loud:

"MLWE is: Given matrix 𝐀 and result 𝐭, find secret vector 𝐬 and error vector 𝐞 such that 𝐀·𝐬 + 𝐞 = 𝐭. The problem is there are too many (𝐬, 𝐞) pairs possible, making it hard to find the true secret!"

Can you work with polynomial MLWE?

Try this simplified examples:

Given:

• Matrix $\mathbf{A} = [[x+1], [x-1]]$
• Matrix $\mathbf{t} = [x² + x]$

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

Let $\mathbf{s} = [x]$ (single entry) Then $\mathbf{A} \cdot \mathbf{s} = [(x+1)x, (x-1)x] = [x² + x, x² - x]$

We want this plus $\mathbf{e}$ to equal $[x² + x, x² + x]$

So $\mathbf{e}$ must satisfy: $[x² + x, x² - x] + \mathbf{e} = [x² + x, x² + x]$

Thus: $\mathbf{e} = [0, (x² + x) - (x² - x)] = [0, 2x]$

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

But there are many more!

---

Key Takeaways

MLWE equation = $\mathbf{A}\mathbf{s} + \mathbf{e} = \mathbf{t}$ (two unknowns!) Given to attacker = $\mathbf{A}$ and $\mathbf{t}$ (public key) Eve's problem = Find $\mathbf{s}$ and $\mathbf{e}$ → Too many possibilities Bob's advantage = Has $\mathbf{s}$ (secret) → Can recover Security reduction = MLWE solves SVP → SVP is hard → MLWE is hard MLWE for ML-KEM = $\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}$ in polynomial ring $R_{3329}$ Parameters = $n=256$, $q=3329$, $k=3$, $\eta=2$ (256-bit security)

---