Why Learning With Errors Is Believed Hard in the Worst Case

Ask what makes a cryptographic problem trustworthy and the usual answer is that many smart people have failed to break it. That is evidence, not an argument: RSA was believed hard for decades on precisely those grounds, and a structured problem with hidden algebraic order was destroyed by an algorithm nobody anticipated. Lattice cryptography is unusual because its hardness claims are the other way around. Breaking a randomly chosen instance of the Learning With Errors problem is at least as hard as solving a worst-case geometric problem, in the sense that any efficient algorithm for the average case can be converted into an efficient algorithm for the hardest instances. The reduction runs in the direction that gives the guarantee.

Two geometric problems that define the lattice family

A lattice is the set of integer linear combinations of a set of basis vectors in $\mathbb{R}^n$. Given a basis, the shortest vector problem asks for the shortest non-zero lattice vector, and the closest vector problem asks, for a target point $t$, for the lattice point nearest to it. Both are hard in a precise sense in high dimension: the best known classical algorithms take time exponential in $n$, with the basis-reduction routines behind them discussed in why LLL and BKZ do not scale making the concrete cost explicit.

A public-key scheme can be built directly from the closest vector problem: the secret is a short “error” vector, the public key is a lattice basis in which the target is close to a lattice point, and recovering the secret means solving the instance. The difficulty with this construction is key size and decryption cost, because the trapdoor that lets the legitimate holder find the close point efficiently is a structured, nearly orthogonal basis that embeds into a large public matrix. Learning With Errors reaches the same security goal through a different interface that composes more cleanly with existing key-exchange protocols.

The average-case problem and its matrix form

The Learning With Errors problem, parameterised by a dimension $n$, a modulus $q$, and an error distribution $\chi$ over $\mathbb{Z}_q$, is stated as follows. A secret vector $s \in \mathbb{Z}_q^n$ is fixed. The solver receives any number of samples $(a_i, b_i)$ where $a_i$ is uniform in $\mathbb{Z}_q^n$ and

$$b_i = \langle a_i, s \rangle + e_i \pmod q,$$

with each $e_i$ drawn independently from $\chi$. The task is to recover $s$. The write-up as a matrix is the same statement: given $A \in \mathbb{Z}_q^{m \times n}$, $b = As + e$, find $s$ or distinguish $b$ from uniform.

The decision version, recover the secret versus distinguish the samples from uniform, matters because the two are polynomially equivalent for suitable parameters, and search-to-decision reductions mean that encryption schemes can be justified from the decision form. The noise vector is what separates the problem from plain linear algebra: without the $e$ term, Gaussian elimination over $\mathbb{Z}_q$ recovers $s$ from $n$ samples in $O(n^3)$ field operations. With it, each sample carries only a small amount of information about $s$, and the errors collectively hide the solution.

Two parameter regimes are worth naming. When $q$ is a large prime and the error distribution is a narrow discrete Gaussian, the problem is called plain LWE. When $q$ is a power of two and the errors are small integers modulo $q$, it is often called Learning With Rounding or the “small modulus” variant. Practical schemes in deployment use a third form: Module-LWE replaces the ring $\mathbb{Z}_q$ with the ring of polynomials $\mathbb{Z}_q[X]/(X^n+1)$, so the secret and the samples are vectors of polynomials and multiplication carries out $\sim n^2$ integer operations in one ring operation. The structure buys smaller keys and faster arithmetic, and the open question is what it costs in security. That trade is the subject of MOD-LWE’s ring structure and its attackers.

What the worst-case reduction actually promises

Regev’s reduction shows that an efficient algorithm solving the average-case decision LWE problem can be turned into an efficient quantum algorithm solving approximate worst-case lattice problems, specifically the gap version of the shortest vector problem with approximation factor $\tilde{O}(n/\alpha)$, where $\alpha$ is the noise rate relative to the modulus. Subsequent work made the reduction classical for certain parameter ranges and tightened the factors. The shape of the statement matters more than the details: hardness is inherited from the worst case, so there is no analogue of the RSA situation where a random modulus might be easy for reasons the field has not spotted. Every instance of LWE is as hard as the hardest lattice instance of matching dimension, and the hardest lattice instance is not defeated by structural attacks for the same reason the average case is: there is nothing to be structured about.

There is a corresponding caveat. The reduction is for the LWE problem itself; the actual cryptographic scheme adds a noise-management construction on top, and the scheme’s parameters must be chosen so that the reduction applies at the same parameter set the implementation uses. The FIPS 203 standard for ML-KEM derives its parameter sets from the Kyber submission, whose security analysis reports estimates against the best known lattice attacks at the target security categories. Those estimates are not proofs; they are the output of the same kind of cryptanalytic effort that eventually broke weaker proposals like NTRU’s early parameter choices, which were shown to be under-parameterised against algebraic and lattice attacks.

The sample count is part of the parameter set

The number of samples $m$ is not a free parameter of the attacker. Given $A$ and $b = As + e$, a solver with $m > n$ samples can subtract multiples of known rows to eliminate the secret entirely, arriving at a set of equations in the error terms alone. The natural approach is to find a linear combination $\sum \lambda_i (a_i, b_i)$ whose $A$-component vanishes, which leaves a linear equation in the $e_i$ with coefficients $\lambda_i$. Each such relation gives one equation in the $n$-dimensional space of errors; with enough relations the error vector is over-determined, and a lattice attack can search for a short solution.

This is exactly where the lattice connection becomes concrete. The set of error vectors that satisfy all the relations forms a lattice of rank $m$ in which the genuine $e$ is short, and recovering $e$ means finding a short vector in a lattice with an added constraint. The attacker’s best algorithms are the basis-reduction routines that also set the security level of the schemes, so the security estimate depends jointly on $n$, $q$, $\alpha$, and how many samples the adversary can obtain. In an encryption scheme the number of samples is bounded by the number of ciphertexts intercepted, which is why key encapsulation is preferable to a raw encryption scheme for LWE-based designs: the KEM restricts the attacker to a single ciphertext per freshly generated key, and the security target is for that one-shot setting.

The standard way to choose parameters is to consult the lattice estimator, an open tool that runs the known attacks against a proposed parameter set and reports the estimated cost in core-Sieve operations. The FIPS 203 submission documents its parameters against that estimator at three security categories, and the numbers are reproduced in the standard. Anyone reading the standard should notice that the parameters are not the largest that fit in the bandwidth budget and not the smallest that beat the estimator; they are a point chosen with margin for foreseeable improvements in attack algorithms.

Why noise must scale with the modulus

The reduction’s approximation factor is $\tilde O(n/\alpha)$ where $\alpha$ is the standard deviation of the error contribution measured against $q$. If the noise is too small relative to $q$, the approximation factor becomes small, which means the reduction bottoms out at a hard lattice problem of enormous approximation factor rather than a moderately hard one. The security claim is not monotone in a single number: growing $\alpha$ increases the difficulty of distinguishing the samples but also increases the chance that legitimate decryption rounds to the wrong value. Every practical parameter set is a point on that curve, with the decryption failure rate bounded below a threshold that the protocol’s error correction and the standard’s analysis tolerate. FIPS 203 specifies parameters for three security levels, and the failure-probability bounds are part of the normative text rather than an implementation detail.