From LWE to the Deployed Schemes

Plain LWE, as defined in The Learning With Errors Problem, is a perfectly good hard problem and a completely impractical cryptosystem. This note explains why, and how two refinements fix it. The second refinement is where the ring from Chapter 1 finally enters the story.

01.The problem with plain LWE

Count the bytes.

A public key in a plain-LWE scheme is essentially the matrix $A$ together with the vector $b$. The matrix has $n$ rows and $n$ columns, so it holds $n^2$ elements of $\mathbb{Z}_q$.

Security requires $n$ in the region of $1000$. Take $n = 1024$ and $q = 3329$, so each element needs $12$ bits. Then

$$1024 \times 1024 \times 12 \text{ bits} \;=\; 12{,}582{,}912 \text{ bits} \;\approx\; 1.5 \text{ MB} .$$

A megabyte and a half, for one public key. An elliptic-curve public key is $32$ bytes. Nothing in a network protocol can absorb a factor of fifty thousand, and no browser is going to download a megabyte to open a connection.

So plain LWE is a proof of concept. The security is real and the object is unusable.

02.Ring-LWE

The fix is to give the problem algebraic structure, and the structure is the ring $R_q = \mathbb{Z}_q[X]/(X^n + 1)$.

Instead of a vector in $\mathbb{Z}_q^n$, a sample uses a single element of $R_q$. A sample becomes

$$(a,\; b = a s + e) \;\in\; R_q \times R_q,$$

where $a$, $s$ and $e$ are all polynomials in $R_q$, and $as$ is polynomial multiplication in that ring, exactly as computed by hand in Chapter 1.

Two things improve at once, and they are the two reasons this ring was chosen.

Size. A single element of $R_q$ carries $n$ coefficients. Where plain LWE needed an $n \times n$ matrix, Ring-LWE needs one polynomial. Storage drops from $n^2$ elements to $n$, a factor of $n$. The megabyte becomes a couple of kilobytes.

The reason is worth seeing rather than accepting. In plain LWE the $n$ rows of $A$ are independent random vectors, so all $n^2$ entries must be stored. In Ring-LWE, multiplying by a fixed polynomial $a$ is a linear operation whose matrix is determined entirely by $a$'s $n$ coefficients, because each successive row is the previous one rotated with a sign flip, which is what $X^n = -1$ does. The matrix is still there. It just no longer needs to be written down.

Speed. Multiplication in $R_q$ has a fast algorithm. Schoolbook multiplication of two degree-$(n-1)$ polynomials costs about $n^2$ coefficient multiplications, which for $n = 256$ is roughly $65{,}000$. The Number Theoretic Transform brings that to about $n \log n$, roughly $2{,}000$ for the same $n$. It is the Fast Fourier Transform carried out in modular arithmetic rather than over the complex numbers.

The structure is not free. Ring-LWE assumes something slightly stronger than plain LWE, because an attacker now has algebraic structure to exploit that plain LWE does not offer. Attacks specific to the ring have been found for some choices of ring, which is one reason $X^n + 1$ with $n$ a power of two is the choice that survived scrutiny.

03.Module-LWE

The standards use a middle setting between the two.

Fix a small module rank $k$. Samples live in $R_q^k \times R_q$, meaning the secret is a short vector of $k$ polynomials rather than a single one. Setting $k = 1$ recovers Ring-LWE. Letting $n = 1$ and $k$ grow recovers plain LWE. Module-LWE interpolates.

The advantage is that security and structure become separately adjustable. The ring dimension $n$ stays fixed at $256$, so one Number Theoretic Transform implementation serves every parameter set. Security is raised or lowered by changing $k$ alone, which means changing how many polynomials are stacked, not how they are multiplied.

That is why ML-KEM has three parameter sets that share almost all of their code. ML-KEM-512, ML-KEM-768 and ML-KEM-1024 use $k = 2$, $3$ and $4$ respectively, over the same $n = 256$ and the same $q = 3329$. ML-DSA does the same with a pair of ranks, using $4 \times 4$, $6 \times 5$ and $8 \times 7$ across its three security levels.

Module-LWE also hedges the assumption. Some structure is retained, so the sizes stay small, but less structure than full Ring-LWE, so any future attack exploiting the ring has less to work with.

04.The assumption, stated exactly

Everything in this chapter now supports one sentence, which is the security claim underneath ML-KEM:

Under the Module-LWE assumption with ring dimension $n = 256$, modulus $q = 3329$, module rank $k \in \{2, 3, 4\}$, and centred binomial error with parameters $\eta_1$ and $\eta_2$, the scheme's public-key encryption cannot be distinguished from random by any polynomial-time adversary, classical or quantum.

Every phrase in it has now been defined except the parameter sets themselves, which Chapter 5 supplies.

05.Chapter summary

A lattice is what you get when a basis is combined with integer coefficients instead of real ones. That one restriction turns a continuous plane into a discrete grid with gaps, and every hard problem here comes from the gaps.

One lattice has infinitely many bases, related by unimodular matrices, and they differ enormously in usefulness. A good basis is short and near-perpendicular, a bad basis is long and nearly parallel, and lattice cryptography puts the good basis in the private key and the bad one in the public key. Basis reduction can always improve a bad basis, and in high dimension it cannot improve it nearly enough.

The determinant measures how spread out a lattice is and does not depend on the basis. Minkowski's theorem turns it into a guarantee that a short vector exists, which means security can never rest on absence, only on difficulty of location.

The shortest vector and closest vector problems are the two hard questions. Both are easy in the plane and neither is solvable in high dimension. Crucially, neither reduces to period-finding, so Shor's algorithm does not apply. The best known quantum attack is Grover's generic square-root speedup, which changes an exponent rather than a category.

Learning With Errors is the algorithmic face of those geometric problems. Simultaneous equations modulo $q$ are trivially solvable, and adding one unit of noise to each equation destroys the solution completely, as the $3 \times 3$ instance over $\mathbb{Z}_{17}$ showed: the noiseless system returned the secret exactly, and the noisy one returned an unrelated point. What is left for an attacker is a closest-vector search. Regev's reduction certifies that random LWE instances are as hard as the worst case of approximate SVP, so there are no weak instances hiding in the distribution.

The noise is drawn from a centred binomial rather than a Gaussian, because it can be sampled with two population counts and no data-dependent branch, which removes an entire family of side-channel attacks at a small cost in proof tidiness.

Plain LWE needs megabyte keys. Ring-LWE collapses them by a factor of $n$ by replacing vectors with elements of $R_q$, and Module-LWE stacks a few of those to tune security without touching the ring.

Which brings the book back to $R_q = \mathbb{Z}_q[X]/(X^n+1)$, built in Chapter 1 with no motivation offered at the time. Chapter 4 explains how to multiply in it quickly, and that transform is the central data path of every implementation and every hardware accelerator that follows.