Lattices.io — Mathematical Lattices & Post-Quantum Cryptography

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, 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 computationally intractable even for quantum computers. And yet, someone who knows the secret can still extract information from the noisy equations, because they know which direction to look.

The Core Idea: Noisy Linear Equations

Without noise, a system of linear equations over integers is easy to solve with Gaussian elimination. You have $$n$$ unknowns, you collect $$m$$ equations, and you can solve exactly. LWE adds a small random integer error to the right-hand side of each equation. The errors are tiny — much smaller than the modulus — but they shatter the algebraic structure that makes Gaussian elimination work.

Definition 15 — LWE Distribution

Fix a dimension $$n$$ , a modulus $$q$$ , and a secret vector $s \in \mathbb{Z}_q^n$ . Each LWE sample consists of:

1. Choose a random row vector $a \in \mathbb{Z}_q^n$ .
2. Compute the dot product $a^\top s \pmod{q}$ .
3. Add a small random error $$e$$ drawn from a narrow Gaussian.
4. Publish the pair $(a,\; b = a^\top s + e \pmod{q})$ .

If you collect many such pairs, you can see that $b \approx a^\top s$ , but the small random $$e$$ prevents you from solving for $$s$$ directly.

Two Versions of the Problem

Search-LWE

Given many LWE samples $$(a_i, b_i)$$ , recover the secret $$s$$ .

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

Decision-LWE

Given $$m$$ pairs $$(a_i, b_i)$$ , decide: were they generated as LWE samples (with a hidden secret), or are they completely random?

Surprisingly, Search and Decision LWE are equivalent in difficulty. If you can tell the difference between LWE and random, you can find the secret $$s$$ .

Why LWE Is Hard: The Reduction from SVP

The crucial theorem — Regev's 2005 result — says: 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.

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

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.