What is Learning With Errors (LWE)?

Learning With Errors is a computational problem introduced by Oded Regev in 2005. Given a system of approximate linear equations over a finite field — where each equation has a small random error added — the goal is to recover the secret vector. The deliberate noise makes the system intractable even for quantum computers, while someone who knows the secret can still decrypt.

What is the difference between LWE and Ring-LWE?

Standard LWE uses unstructured random matrices, resulting in large key sizes. Ring-LWE restricts the algebra to polynomial rings, which dramatically reduces key sizes and improves performance while preserving security. Module-LWE (used in Kyber/ML-KEM) is a middle ground that uses small matrices of ring elements, balancing efficiency with security flexibility.

Why is LWE considered quantum-resistant?

LWE's security reduces to worst-case lattice problems like approximate SVP, which no known quantum algorithm can solve efficiently. Shor's algorithm, which breaks RSA and ECC, exploits the algebraic structure of factoring and discrete logarithms — structure that LWE deliberately avoids by adding random noise. This makes LWE the basis for most NIST post-quantum standards.

Learning With Errors (LWE), Ring-LWE and Module-LWE

Suppose you want to hide a secret number. One approach: multiply your secret by random numbers and give out the products. That’s essentially what public-key cryptography has done for decades. The problem is that if the math is too clean, a quantum computer can unravel it (that’s Shor’s algorithm).

Learning With Errors (LWE), introduced by Oded Regev in 2005 (for which he received the 2018 Gödel Prize), takes a different approach: deliberately introduce random noise into the equations. The equations become just slightly wrong — a small random error is added to each one. This tiny perturbation, it turns out, makes the whole system hard to solve with the best classical and quantum methods known today when parameters are chosen carefully. And yet, someone who knows the secret can still extract information from the noisy equations, because they know which direction to look.

Intuition

Imagine guessing someone’s bank balance by asking them, where every answer is off by a small random amount, like $1 or $2. Ask 100 times and the average gives you the exact number.

Learning With Errors (LWE) is a harder version of this game. The secret is a vector, each answer is a random linear equation in it plus a small error, and all arithmetic wraps around modulo q, so averaging no longer helps. Without the errors, Gaussian elimination would recover the secret from a handful of equations. With them, no efficient algorithm is known, classical or quantum, which is why LWE is used for post-quantum encryption.

Secret s = (?, ?) · modulus q = 97 · each row is b = a₁s₁ + a₂s₂ + e (mod 97)

#	a = (a₁, a₂)	b	hidden error e
1	(27, 52)	40	?
2	(61, 48)	95	?
3	(75, 11)	42	?

What to notice: Without noise, recovering s is high-school linear algebra: n equations, n unknowns, done. A few units of noise make elimination useless, and the attacker is left searching for the secret that best explains every noisy equation — a bounded-distance decoding (closest-vector) problem on a lattice. Here brute force over q² = 9,409 secrets still works; ML-KEM uses n = 256·k (k = 2, 3, 4) with q = 3329, so the secret has at least 512 unknown coordinates, guessing is hopeless, and the best known attacks are lattice reduction.

The LWE Distribution

The formal definition of LWE pins down every parameter: the dimension, the modulus, and the error distribution. All three must be chosen together — they determine both security and correctness.

Definition 15 — The LWE Distribution

Fix parameters: dimension $n \geq 1$ , modulus $q \geq 2$ , and an error distribution $\chi$ over $\mathbb{Z}_q$ (typically a discrete Gaussian $D_{\mathbb{Z}, \sigma}$ with standard deviation $\sigma \ll q$ ).

For a secret $s \in \mathbb{Z}_q^n$ , the LWE distribution $A_{s,\chi}$ is the distribution over pairs $(a, b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$ obtained by:

1. Sample $a \leftarrow \mathbb{Z}_q^n$ uniformly at random.
2. Sample error $e \leftarrow \chi$ .
3. Output the pair $(a,\; b = a^\top s + e \pmod{q})$ .

Equivalently, in matrix form: given $m$ samples, the distribution produces $(A, b) = (A, As + e)$ where $A \in \mathbb{Z}_q^{m \times n}$ is a random matrix, $s \in \mathbb{Z}_q^n$ is the fixed secret, and $e \in \mathbb{Z}_q^m$ is a vector of independent errors from $\chi$ .

The parameters $(n, q, \chi)$ fully specify the hardness of the LWE problem: larger $n$ and smaller $\sigma/q$ increase security; larger $q$ increases correctness margin.

Decision vs Search LWE and the Equivalence

LWE has two natural formulations — one asks you to find the secret, the other asks you to detect whether a given sample is an LWE sample at all. Remarkably, these two problems are computationally equivalent.

Search-LWE

Given polynomially many samples $(a_i, b_i) \leftarrow A_{s,\chi}$ , find the secret $s \in \mathbb{Z}_q^n$ .

This is directly analogous to solving a noisy linear system. Without noise, it’s trivial via Gaussian elimination. With noise — believed infeasible in high dimension, even for quantum computers.

Decision-LWE

Given $m$ pairs $(a_i, b_i)$ , decide: are they from $A_{s, \chi}$ for some hidden $s$ , or are they uniformly random in $\mathbb{Z}_q^n \times \mathbb{Z}_q$ ?

Security of encryption requires Decision-LWE to be hard: if an attacker can distinguish LWE ciphertexts from random strings, they can recover information about the plaintext.

Theorem — Search-LWE and Decision-LWE Are Equivalent

For prime modulus $q$ and any error distribution $\chi$ with polynomially bounded support:

If there exists a polynomial-time algorithm solving Decision-LWE, then there exists a polynomial-time algorithm solving Search-LWE (Regev 2005, refined by Micciancio and Mol 2011).

The reduction works by a hybrid argument: given a Decision-LWE oracle, one can recover each coordinate of $s$ independently by querying samples where one row of $A$ is shifted by a test vector. The decision oracle detects whether this shift is consistent with the current guess for $s_i$ .

Consequence: to prove a scheme is semantically secure (indistinguishable under chosen-plaintext attack), one assumes Decision-LWE is hard. That is the stronger assumption: Decision-hard trivially implies Search-hard (anyone who can recover $s$ can also tell LWE samples from random). The equivalence says the extra strength costs nothing, because Decision-LWE is hard whenever Search-LWE is.

Why LWE Is Hard: The Reduction from SVP

The key result is Regev’s 2005 theorem: if you can solve LWE, you can solve the hardest possible SVP instances using a quantum computer. This is a “worst-case to average-case” reduction. It means that LWE is not just a random hard problem someone cooked up — its hardness is tied, provably, to the hardness of lattice problems that have been studied for over a century.

In practical terms: breaking Kyber or Dilithium implies you can find the shortest vector in arbitrary high-dimensional lattices efficiently using a quantum computer. Since we believe that’s impossible, we believe LWE is hard.

Module-LWE (MLWE) — Used in Kyber

The version of LWE used in Kyber (ML-KEM, FIPS 203) is neither plain LWE nor Ring-LWE but a middle ground called Module-LWE. It combines the efficiency of Ring-LWE with a stronger hardness assumption, and adds a tunable security parameter.

Definition — Module-LWE (MLWE)

Let $R_q = \mathbb{Z}_q[x]/(x^n + 1)$ be the NTRU-style polynomial ring. Fix a module rank $k \geq 1$ .

The Module-LWE distribution over $R_q^k \times R_q$ is defined as follows: sample secret $s \in R_q^k$ (a vector of $k$ ring elements with small coefficients), sample $a \leftarrow R_q^k$ uniformly, sample error $e \leftarrow \chi$ over $R_q$ , and output $(a,\; b = a^\top s + e) \in R_q^k \times R_q$ .

In matrix form: the public key matrix is $A \in R_q^{k \times k}$ and the LWE relation is $b = As + e$ for vectors in $R_q^k$ . Each ring element encodes $n$ scalar LWE equations, so the full system has $kn$ equations in $kn$ unknowns.

Module rank $k$ controls security:
— $k = 2$ : ML-KEM-512 (~128-bit security, fastest)
— $k = 3$ : ML-KEM-768 (~192-bit security, recommended)
— $k = 4$ : ML-KEM-1024 (~256-bit security, highest)

Hardness: MLWE with rank $k$ reduces to worst-case SVP on module lattices — lattices with rank- $k$ module structure over $R$ . As $k \to \infty$ , MLWE approaches plain LWE (strongest hardness); at $k = 1$ it is Ring-LWE (most efficient).

LWE Parameter Selection for 128-Bit Security

Choosing LWE parameters is a precise engineering task, not a guess. The standard methodology uses the Lattice Estimator tool (Albrecht et al.) to model the cost of all known attacks — primal, dual, and hybrid — and find the parameter set that minimizes key/ciphertext sizes while keeping all attack costs above the target security level.

Parameter Selection for 128-Bit Classical Security

The three parameters $(n, q, \sigma)$ must satisfy several constraints simultaneously:

Dimension $n$ : Must be large enough that the best BKZ attack on the primal lattice costs $\geq 2^{128}$ operations. For Kyber with $k=3$ , the effective LWE dimension is $n \cdot k = 768$ . The BKZ block size needed to break this (round-3 Kyber specification) is $\beta \approx 623$ , with Core-SVP cost $2^{0.292 \cdot 623} \approx 2^{182}$ classically. For comparison, Kyber-512 needs $\beta \approx 406$ ( $\approx 2^{118}$ ) and Kyber-1024 $\beta \approx 873$ ( $\approx 2^{256}$ ). Core-SVP counts only a single SVP call, so it is a conservative lower estimate: Kyber-512’s $2^{118}$ is still argued to meet NIST Level 1 once the full attack cost is counted.

Modulus $q$ : Must be large enough that the message encoding $(\lfloor q/2 \rceil \cdot m)$ does not get overwhelmed by the accumulated error after decryption. For Kyber: $q = 3329$ (a prime chosen so that $q \equiv 1 \pmod{256}$ for efficient NTT).

Error parameter $\sigma$ : In Kyber, the error distribution is a centered binomial distribution $B_\eta$ with $\eta = 2$ or $3$ , giving $\sigma \approx \sqrt{\eta/2} \approx 1$ . This is much smaller than the Gaussian used in theoretical constructions, optimized for efficiency.

Security vs correctness tradeoff: Larger $\sigma$ makes the problem harder (better security) but increases decryption failure probability. The failure probability must be kept below $2^{-128}$ to prevent attacks that exploit decryption failures. This pins $\sigma$ in a narrow window.

Quantum security factor: Parameters are chosen with a security margin: classical Core-SVP security ~182 bits, quantum ~165 bits for ML-KEM-768 (a Level 3 parameter set). Both are far above the 128-bit baseline, providing a buffer against algorithmic improvements.

LWE Parameters: The Three Knobs

Three numbers control the security and performance of any LWE-based scheme. Getting them right is the difference between a secure system and one that can be broken in hours.

Definition 16 — LWE Parameter Set (n, q, σ)

Dimension n — the number of unknowns. Bigger $n$ means more security (exponentially harder to solve) but larger keys and slower operations. Typical values: $n = 512$ to $2048$ .

Modulus q — all arithmetic is done mod $q$ . Must be large enough that the signal (the encrypted message) is not overwhelmed by noise, but not so large that security decreases. Often a prime near $n^2$ to $n^{2.5}$ .

Noise width σ — the standard deviation of the error distribution. Smaller $\sigma$ makes decryption more accurate; larger $\sigma$ makes the problem harder. The ratio $\sigma/q \approx 1/n$ is the sweet spot for most schemes.

LWE-Based Encryption: The Basic Construction

Here is the simplest possible LWE encryption scheme, due to Regev. It encrypts one bit at a time and illustrates the core idea behind all LWE-based schemes.

Construction 1 — Regev Encryption

Key generation: Sample a secret $s \in \mathbb{Z}_q^n$ . Sample a matrix $A$ of random LWE rows and publish $(A,\; b = As + e)$ as the public key.

Encrypt a bit $\mu \in \{0,1\}$ : Choose a random subset of the published LWE rows, sum them up, and add $\mu \cdot \lfloor q/2 \rfloor$ to the right side. This hides the bit in a random-looking sum.

Decrypt: Compute $c_2 - c_1^\top s$ . The errors cancel approximately, leaving something close to 0 (if $\mu = 0$ ) or close to $q/2$ (if $\mu = 1$ ). Round to recover the bit.

Ring-LWE: The Same Idea, Much More Efficient

Plain LWE has a problem: the public key is a matrix with $n^2$ entries — that’s megabytes of data for cryptographic parameters. Ring-LWE fixes this by doing all the arithmetic inside a polynomial ring instead of plain integers. The key insight: a single ring element encodes the same information as an entire LWE matrix, thanks to the structure of polynomial multiplication.

Definition 17 — Ring-LWE

Replace $\mathbb{Z}_q^n$ with the polynomial ring $R_q = \mathbb{Z}_q[x]/(x^n + 1)$ — polynomials of degree less than $n$ , with coefficients reduced mod $q$ , and the polynomial itself reduced mod $x^n + 1$ .

A Ring-LWE sample is a pair $(a, b = a \cdot s + e) \in R_q \times R_q$ where multiplication is polynomial multiplication in $R_q$ . One ring element encodes $n$ scalar LWE equations simultaneously. Key sizes drop from $O(n^2)$ to $O(n \log q)$ .

The tradeoff: Ring-LWE operates on ideal lattices (lattices with ring structure), which have more algebraic symmetry than general lattices. Theoretically, this could be exploited. In practice, no attack has broken Ring-LWE at standard parameters, but it’s considered a slight weakening of the hardness assumption compared to plain LWE.

Module-LWE: The Best of Both Worlds

A small worked example of both variants, with the matrix that one polynomial replaces, is in 6.7 Ring-LWE and Module-LWE.

Module-LWE is the version used by Kyber and Dilithium. It’s Ring-LWE but over a module of rank $k$ — think of it as a $k \times k$ matrix of ring elements instead of a single ring element. This lets you tune security by adjusting $k$ without changing the ring structure.

LWE (plain)

Works over integers. Keys: $O(n^2)$ bits. Strongest hardness assumption (general lattices). Slow and large — mainly used for theoretical constructions and FHE, not practical key exchange.

Ring-LWE

Works over one polynomial ring element. Keys: $O(n \log q)$ bits. Fast (NTT multiplication). Slight algebraic structure concern. Used in early PQC schemes like NewHope.

Module-LWE (Kyber)

Works over a $k \times k$ matrix of ring elements. Keys: $O(k^2 n \log q)$ bits. Tunable security via $k$ . Stronger hardness than Ring-LWE. The NIST-selected standard for key encapsulation.

The NTT: Why Ring-LWE Is Fast

Multiplying two degree- $n$ polynomials naively takes $O(n^2)$ multiplications. Ring-LWE schemes would be impractically slow at large $n$ without a trick: the Number Theoretic Transform (NTT). The NTT is like a Fourier transform but for integers modulo a prime. It converts a polynomial into its “frequency domain” in $O(n \log n)$ operations. Multiplication in the NTT domain is element-wise — just multiply corresponding frequencies — then convert back. Kyber uses the NTT with $n = 256$ and $q = 3329$ , chosen so that the NTT is especially efficient. This is why Kyber key exchange is faster than X25519 despite using larger objects.

Check Your Understanding

Q1. Without the error term, b = As mod q could be solved with Gaussian elimination. What does adding a small random error e change?
Q2. What happens if a designer makes the error σ too large relative to q?
Q3. In Regev encryption, why can the key holder decrypt while an eavesdropper cannot?
Q4. Why does Kyber use Module-LWE instead of plain LWE or Ring-LWE?

← Previous2.2Closest Vector Problem Next →2.4Short Integer SolutionWhen even a short answer is impossibly hard to find.

Unfamiliar symbol? The math reference explains the notation used across the site.

Found a mistake or something unclear? Report it on GitHub or email hello@ovasylenko.com.