The Core Equation: $t = As + e$

ML-KEM's security, and the entire Learning With Errors (LWE) family of cryptographic primitives, rests on a single equation. NIST's own draft standard describes it directly:

In the LWE problem, the input is a set of random noisy linear equations in some secret variables $x$, and the task is to recover $x$ — the noise in the equations is such that standard algorithms like Gaussian elimination are intractable.

In ML-KEM's actual key generation, this takes the concrete form:

$$t = As + e \pmod{q}$$

Per the FIPS 203 specification itself: "the secret key $s$ is a set of secret variables, while the encryption key is a collection of noisy linear equations $(A, As + e)$ in the secret variables $s$."

The Components

What Makes This Equation Special

The structure is deliberately unbalanced. The defender knows $s$ and $e$ because they chose them. An attacker sees only $A$ and $t$. To recover $s$, they must solve:

$$t \approx As \pmod{q}$$

where "$\approx$" masks the fact that each equation is wrong by an unknown, small amount. The attacker cannot tell how much of $t$ is signal versus noise.

Without the error term — if $e = 0$ — the system collapses to $t = As$, an exact linear system solvable by Gaussian elimination in polynomial time. No quantum computer required; a laptop does it. The error term is what elevates the problem from trivial to (presumed) intractable.

The Geometric Interpretation

The equations describe a lattice point $As$ in high-dimensional space, blurred by a small Gaussian ball of noise. The attacker must find the lattice point closest to a given target $t$ — the closest vector problem (CVP) — a geometric search problem with no known efficient algorithm, classical or quantum.

This geometric framing is also where the formal security guarantee comes from. The hardness of LWE is supported by reductions from worst-case lattice problems such as GapSVP and SIVP — both are geometric problems about finding short or nearby points in high-dimensional lattices, believed intractable for classical and quantum computers alike.

What $q$ Means

The modulus $q$ defines the size of the number space. All operations happen modulo $q$, meaning values wrap around when they exceed $q$. A large $q$ relative to the noise provides more room for the error to hide, strengthening security. The choice of $q$ is one of the key parameters that distinguishes ML-KEM's three security levels.