Learning With Errors: The Distribution, the Decision-Search Equivalence, and Regev's Reduction

The most consequential idea in post-quantum cryptography can be stated in one sentence: take a system of linear equations over a finite field, perturb each equation by a small random error, and recovering the unknowns becomes hard. Without the error, a first course in linear algebra dispatches the problem — Gaussian elimination reads off the secret. With a small error added to every equation, elimination amplifies the noise catastrophically and fails, and no efficient algorithm is known to succeed instead. This is the Learning With Errors problem, and its remarkable property, proved by Regev, is that solving it on random instances would let you solve the hardest lattice problems in the worst case. This article develops the distribution, its two forms, that reduction, and the lattice picture behind it.

The LWE distribution

Fix a dimension n, a modulus q, and a secret vector s with entries modulo q. An LWE sample is produced by drawing a uniformly random vector a with n entries modulo q, computing its inner product with the secret, and adding a small error drawn from an error distribution — typically a discrete Gaussian narrow relative to q. The sample is the pair consisting of a and the noisy inner product b. Repeat to obtain as many samples as wanted, all sharing the same secret but each with fresh randomness and fresh error.

The search version of the problem asks: given many such samples, recover the secret s. The parameters that govern hardness are the dimension n, which sets the problem size; the modulus q, which sets the arithmetic; and the width of the error distribution, usually written as a fraction alpha of q. The error must be small enough that decryption can eventually cancel it, yet large enough that it genuinely obstructs recovery — the entire art of parameter selection lives in that tension, taken up in a later article.

It is worth noticing what LWE is not. It is not a structured or algebraic problem in this plain form; the vectors a are unconstrained and uniform. That lack of structure is a feature: it means the hardness rests on generic lattices rather than special algebraic families, and it is the baseline against which the structured, more efficient variants of the next article are measured.

Why the noise is everything

Delete the error and the problem collapses. With exact equations, gathering n linearly independent samples yields a square system whose solution is the secret, found by Gaussian elimination in polynomial time. The secret is not hidden at all; it is merely encoded in a solvable linear system. Every bit of LWE's hardness therefore comes from the error term, which converts exact equations into approximate ones.

The reason elimination fails on noisy equations is that it takes linear combinations of rows, and each combination sums the independent errors of the rows it uses. To isolate one coordinate of the secret, elimination must combine many equations, and the accumulated error swamps the signal — the recovered value is buried under noise proportional to the number of combined samples. Small per-equation error, amplified across the many combinations elimination requires, defeats the direct attack.

This is why the width of the error is a security parameter and not an implementation nuisance. Too little noise and the linear structure leaks; too much and legitimate decryption cannot recover the message. The scheme is a controlled exploitation of the fact that a little noise, correctly sized, is catastrophic for the attacker's linear algebra while remaining survivable for the legitimate holder of the secret.

Search, decision, and their equivalence

LWE comes in two forms. Search-LWE is the recovery problem already stated: find the secret from the samples. Decision-LWE is weaker on its face: given a collection of pairs, decide only whether they are genuine LWE samples for some secret or are uniformly random pairs with no secret at all. Cryptography usually needs the decision form, because semantic security — the guarantee that ciphertexts leak nothing — is naturally phrased as the indistinguishability of real from random.

The pivotal fact is that these two forms are equivalent for appropriate moduli. Regev showed that for a prime modulus bounded by a polynomial in n, an algorithm that solves decision-LWE can be turned into one that solves search-LWE, and the converse is immediate. The search-to-decision direction proceeds by guessing the secret one coordinate at a time: a decision oracle can be used to test a guessed value of a coordinate by transforming the samples so that a correct guess leaves them LWE-distributed and an incorrect guess randomizes them.

The equivalence means designers may build on the convenient decision form while inheriting the hardness of the search form, and ultimately of the worst-case lattice problems beneath it. The two views are one problem seen from two angles: recover the secret, or merely notice that a secret is present.

Regev's worst-case reduction

The reason to trust LWE is a theorem, not merely the failure of attacks. Regev proved a quantum reduction: any efficient algorithm solving average-case LWE, for suitable parameters, can be converted into an efficient quantum algorithm solving the worst-case lattice problems GapSVP and the shortest independent vectors problem, to within an approximation factor polynomial in the dimension. Because those worst-case problems are believed to have no efficient algorithm — classical or quantum — average-case LWE is believed hard.

Two qualities of this reduction deserve emphasis. First, it is worst-case to average-case: it relates a random LWE instance to the hardest lattice of the dimension, so there are no weak random instances a scheme might accidentally generate. Second, it targets approximation factors polynomial in n, precisely the regime the previous article identified as believed hard and unimproved by quantum computers. The reduction is quantum — the algorithm it constructs uses quantum steps — which is why LWE's worst-case guarantee is stated against quantum lattice hardness.

The practical upshot is that the security of the standardized schemes does not rest on the empirical observation that people have failed to break them. It rests on a chain: break the scheme, and you break average-case LWE; break average-case LWE, and you have a quantum algorithm for worst-case lattice problems that decades of effort suggest does not exist.

LWE as bounded-distance decoding

The lattice picture makes the connection concrete. Stack many sample vectors as the rows of a matrix and consider the q-ary lattice they define — the set of integer vectors consistent with those rows modulo q. The vector of noisy values b is then a point that lies close to, but not exactly on, this lattice: it equals an exact lattice point, the noiseless inner products, displaced by the small error vector. Recovering the secret is finding that nearby lattice point, which is the bounded-distance decoding problem — a promise version of the closest vector problem where the target is guaranteed to sit within a small radius.

The radius is the size of the error, roughly the error width times the square root of the number of samples. When this radius is small relative to the lattice's minimum distance, the nearest lattice point is unique and decoding is well posed; the hardness is that finding it, without the good basis that a secret key would provide, is exactly the lattice search the previous article described. LWE is thus not a new hardness assumption bolted onto lattices but a particularly clean average-case face of the same closest-vector geometry.

From here, encryption follows quickly. A public key is a batch of LWE samples; encrypting a bit adds a subset of them together and nudges the result by half the modulus when the bit is one; the holder of the secret subtracts the inner product, sees whether the residue is near zero or near half the modulus, and reads the bit — the small errors cancel because they stay below the decoding radius. The noisy linear algebra that defeats the attacker is survived by the key holder with room to spare, and that gap is the whole cryptosystem.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

lwe_instance:
  dimension_n: n
  modulus_q: prime_poly_bounded
  error_width_alpha: small_fraction
  form: decision      # equivalent to search for this q
correctness:
  error_below_decoding_radius: true
hardness:
  worst_case_target: [GapSVP, SIVP]
  reduction: regev_quantum
  primary_source: cited

Glossary

LWE sample

A pair (a, b) with a uniform over Z_q^n and b the inner product of a with a secret plus a small error modulo q.

Error distribution (chi)

The narrow distribution, usually a discrete Gaussian of width a small fraction of q, from which each equation's perturbation is drawn.

Search-LWE / Decision-LWE

Recover the secret from samples, versus merely distinguish genuine samples from uniformly random pairs; equivalent for suitable moduli.

Worst-case-to-average-case reduction

Regev's quantum proof that solving random LWE instances would solve the hardest lattice problems of the dimension.

Bounded-distance decoding (BDD)

A closest-vector problem where the target is promised to lie within a small radius of the lattice, matching the LWE noise.

q-ary lattice

The lattice of integer vectors consistent modulo q with a given set of sample rows; LWE's noisy vector lies near one of its points.

References

1. Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (JACM, 2009)
2. Lyubashevsky, Peikert & Regev, On Ideal Lattices and Learning with Errors over Rings (EUROCRYPT, 2010)
3. Albrecht, Player & Scott, On the Concrete Hardness of Learning with Errors (IACR ePrint 2015/046)
4. Langlois & Stehle, Worst-Case to Average-Case Reductions for Module Lattices (Designs, Codes and Cryptography, 2015)
5. NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (2024)