Ring Lattices & Module-LWE

From Vectors to Polynomials

The two problems assembled in the previous pages, the short-integer-solution problem and learning with errors, are hard, reduction-grounded, and conjecturally quantum-resistant, but they are not yet efficient enough to deploy. The obstruction is size. A single learning-with-errors sample is one noisy scalar \(\langle \mathbf{s}, \mathbf{a} \rangle + e \in \mathbb{Z}_q\), extracted from a fresh random vector \(\mathbf{a} \in \mathbb{Z}_q^n\). Producing enough pseudorandomness to encrypt a message therefore costs a matrix of independent random entries, and every operation is a full matrix-vector product. Keys grow as \(n^2\), and arithmetic with them is quadratic.

This page removes that cost by changing the algebraic home of the samples. The flat vector space \(\mathbb{Z}_q^n\) is replaced by a quotient of a polynomial ring, in which a single element carries \(n\) coordinates at once and multiplication mixes them all in near-linear time.

The Ring \(R = \mathbb{Z}[x]/(f(x))\)

The construction reuses two objects already built in the algebra pages. The first is the polynomial ring \(\mathbb{Z}[x]\), whose elements are formal integer-coefficient polynomials. The second is the factor ring construction, which collapses a ring modulo an ideal. Fix a monic polynomial \(f(x) \in \mathbb{Z}[x]\) of degree \(n\), and let \((f(x))\) denote the principal ideal it generates, that is, the set of all polynomial multiples of \(f\). The ring at the center of this page is the quotient \[ R = \mathbb{Z}[x]/(f(x)). \]

Passing to this quotient imposes a single relation, \(f(x) = 0\). Every polynomial is reduced modulo \(f\), so each residue class has a unique representative of degree less than \(n\), and because \(f\) is monic, the division that produces it introduces no denominators. As an additive group, then, \(R\) is isomorphic to \(\mathbb{Z}^n\). An element is determined by its \(n\) integer coefficients \((a_0, a_1, \ldots, a_{n-1})\). What the polynomial structure adds beyond \(\mathbb{Z}^n\) is a multiplication that the flat vector space does not possess. The product of two residues is formed as polynomials and reduced again modulo \(f\).

Reducing the coefficients modulo an integer \(q\) in turn gives the finite ring \[ R_q = R/qR = \mathbb{Z}_q[x]/(f(x)), \] whose elements are degree-\(\lt n\) polynomials with coefficients drawn from \(\mathbb{Z}_q\). This \(R_q\) is the polynomial analogue of the coordinate space \(\mathbb{Z}_q^n\) that hosted the earlier problems: additively identical to it, but now closed under a ring multiplication. A random element of \(R_q\) is a single object that stands in for a full random vector, and this is the source of the compression to come.

The Choice of \(f\)

The modulus polynomial \(f\) is not arbitrary. Two families recur throughout the theory. The first is \(f(x) = x^n - 1\), which makes multiplication by \(x\) act as a cyclic shift of the coefficient vector and so gives the ring a circulant structure. The second, and the one adopted by the key-encapsulation standard of the final section, is \(f(x) = x^n + 1\) with \(n\) a power of two. This \(f\) is a cyclotomic polynomial, whose complex roots are the primitive \(2n\)-th roots of unity, the points \(e^{i\pi(2k+1)/n}\) evenly spaced on the unit circle. The polynomial \(x^n + 1\) is also irreducible over \(\mathbb{Q}\). Substituting \(x + 1\) for \(x\) does not affect irreducibility, since the substitution is invertible and preserves degrees. Modulo \(2\), squaring is additive, so \((x + 1)^n \equiv x^n + 1\) because \(n\) is a power of two. The polynomial \((x + 1)^n + 1\) therefore has leading coefficient \(1\), every other coefficient even, and constant term \(2\), and Eisenstein's criterion at the prime \(2\) applies. Irreducibility makes the quotient \(\mathbb{Q}[x]/(f)\) a field. Since \(R\) sits inside that field, again because division by the monic \(f\) introduces no denominators, \(R\) is free of the zero divisors that a reducible \(f\) would introduce, a property the hardness discussion below will need.

Multiplication modulo \(x^n + 1\) is negacyclic. Shifting past the top degree wraps around with a sign flip, since \(x^n \equiv -1\). Concretely, for \(a, b \in R\) the product coefficients are \[ (a \cdot b)_k = \sum_{i+j=k} a_i b_j - \sum_{i+j=k+n} a_i b_j, \] the first sum collecting the ordinary convolution terms and the second the wrapped terms that cross degree \(n\), negated. A naive evaluation of this product is still quadratic in \(n\). The near-linear speed advertised above comes from evaluating it through a fast transform, a point the final section makes precise once the standardized parameters are in view.

One Ring Element for Many Scalars

The structural payoff is already visible at the level of counting. In the coordinate world, a random \(\mathbf{a} \in \mathbb{Z}_q^n\) is \(n\) independent scalars, and pairing it with a secret produces a single pseudorandom scalar. In the ring world, a random \(a \in R_q\) is likewise \(n\) coefficients. Multiplying it by a secret ring element \(s \in R_q\), however, produces another full ring element \(a \cdot s \in R_q\), that is, \(n\) pseudorandom scalars at once. The ring multiplication has taken a single random object and manufactured a vector's worth of output from it.

The price is that these \(n\) output scalars are no longer independent. They are the coordinates of one product in a structured ring, tied together by the relation \(f(x) = 0\). Every efficiency this page gains, and every specialization of the hardness assumption it must accept in exchange, traces back to that single trade of independence for structure.

Fixing the basis \(1, x, \ldots, x^{n-1}\) makes this correspondence mechanical. Multiplication by a fixed \(a \in R_q\) is a linear map on \(\mathbb{Z}_q^n\), represented by a structured \(n \times n\) matrix whose columns are the successive shifts of \(a\) (cyclic for \(x^n - 1\), negacyclic for \(x^n + 1\)). A single ring element thus encodes an entire structured matrix, and a single ring equation encodes \(n\) scalar equations of the earlier kind. The next section installs the two problems that live in this ring, each the direct polynomial image of one built before.

Ring-SIS and Ring-LWE

Each of the two lattice problems from the previous pages has a direct image in the ring \(R_q\), obtained by the same substitution throughout. A random vector from \(\mathbb{Z}_q^n\) becomes a single random element of \(R_q\), and an inner product of vectors becomes a product in \(R_q\). What was a matrix of \(nm\) independent scalars becomes a short list of \(m\) ring elements, and the hardness assumption narrows accordingly.

The Ring Analogue of the Hash

The short integer solution problem sought a short integer combination of random vectors summing to zero. Its ring form replaces the vectors by ring elements and the integer combination by a combination with short ring coefficients.

The compression is immediate from the counting of the previous section. Because a single random \(a_i \in R_q\) already carries \(n\) coordinates and multiplication by it acts as a full \(n \times n\) structured matrix, the number of ring samples needed to guarantee a short solution is smaller than the coordinate count by a factor of \(n\). The coordinate problem needed \(m \approx n \log q\) columns, whereas here \(m \approx \log q\) ring elements suffice. The matrix that the coordinate problem stored explicitly is now generated on demand from \(m\) polynomials.

The Ring Analogue of the Encryption

Learning with errors hid a secret behind noisy inner products. Its ring form hides a secret ring element behind noisy ring products. The error is then no longer a single scalar but a small element of the ring, a polynomial all of whose coefficients are drawn from the error distribution.

As in the coordinate case, the problem that matters for building pseudorandomness is not the search form but the decision form. What is demanded is that the samples be indistinguishable from pure randomness, not merely that the secret be hard to recover.

The same compression the hash enjoyed carries over. One Ring-LWE sample \((a_i, b_i)\) delivers a full pseudorandom ring element \(b_i \in R_q\), worth \(n\) pseudorandom scalars, from a single random \(a_i\) and one near-linear ring multiplication. Coordinate learning with errors produced only a single scalar per random vector. This is the efficiency the coordinate problems could not supply, and it is bought entirely with the algebraic structure of \(R_q\).

Ideal Lattices and Hardness

The coordinate problems earned their credibility by reduction. Solving them on random instances was shown at least as hard as solving lattice problems in the worst case. The ring problems must earn the same credibility, and the argument follows the same shape. The lattices it reaches, however, are no longer arbitrary. They carry the algebraic symmetry of the ring, and that symmetry both sharpens the geometry and narrows the class of instances the guarantee covers.

From Ring Ideals to Lattices

The geometric object attached to the ring is built from its ideals. Recall that an ideal of a ring is an additive subgroup closed under multiplication by every ring element. Fix the coefficient-vector identification of the first section, sending each element of \(R\) to its coordinate vector in \(\mathbb{Z}^n\). Under this map, an ideal \(I \subseteq R\), being in particular an additive subgroup of \(R \cong \mathbb{Z}^n\), becomes an additive subgroup of \(\mathbb{Z}^n\). That subgroup is discrete, since distinct integer vectors lie at distance at least \(1\), so by the characterization of lattices as discrete additive subgroups it is a lattice in \(\mathbb{Z}^n\). A lattice arising this way is called an ideal lattice.

The extra closure is what distinguishes an ideal lattice from a generic one, and its geometric consequence is a hidden symmetry. Because an ideal is closed under multiplication by \(x\), and multiplication by \(x\) is a coordinate shift (cyclic for \(f = x^n - 1\), negacyclic for \(f = x^n + 1\)), an ideal lattice is mapped to itself by that shift. A single short vector in such a lattice therefore generates a whole orbit of \(n\) short vectors, its successive shifts, all of the same length. Generic lattices have no such structure. In a generic lattice, a short vector tells one nothing about the location of others.

The Worst-Case Guarantee

With ideal lattices in hand, the hardness of Ring-LWE is stated by exact analogy to the coordinate worst-case hardness theorem. The reduction is again quantum, and the target is again an approximate shortest-vector problem, now restricted to the ideal lattices of the ring.

The statement mirrors its coordinate ancestor, and its decisive change is that the guarantee ranges over every ideal lattice rather than every lattice. The target problem also becomes \(\mathrm{SVP}_\gamma\), but for \(f = x^n + 1\) little is lost. Multiplication by a nonzero element is invertible in the field \(\mathbb{Q}[x]/(f)\), so the \(n\) shifts of a shortest vector are linearly independent, and they all have the same length. That restriction to ideal lattices is the entire content of the trade made in the first section.

The proof again proceeds in two stages. A quantum reduction first establishes the hardness of the search problem for any ring of integers of a number field. A classical search-to-decision step then uses the special algebraic structure of cyclotomic rings, namely that the number field they generate is Galois over the rationals and that the modulus splits into small-norm prime ideals. The precise form of the error distribution the reduction requires is delicate, most naturally expressed through the geometry of the ring described below. The full argument is beyond the scope of this page. What matters here is the shape of the conclusion and the object it reaches.

The Geometry of the Ring

One subtlety in the hardness statement deserves a closer look: what "short" means for a ring element. The coefficient embedding of the first section, reading an element as its vector of coefficients and taking the ordinary Euclidean norm, is the naive choice, and it suffices for building intuition. But it behaves badly under multiplication. The norm of a product \(a \cdot b\) can be only loosely related to the norms of \(a\) and \(b\), because each coefficient of a product mixes every coefficient of both factors.

The sharper notion, and the one the hardness reduction actually uses, is the canonical embedding. Rather than reading off coefficients, it evaluates a ring element \(z\) at all \(n\) complex roots \(\alpha_1, \ldots, \alpha_n\) of \(f\), sending \(z \mapsto (z(\alpha_1), \ldots, z(\alpha_n)) \in \mathbb{C}^n\). For the cyclotomic \(f = x^n + 1\), these roots are the evenly spaced points on the unit circle named in the first section. The virtue of this map is that it turns ring multiplication into coordinate-wise multiplication of the image vectors, because evaluating a product at a fixed root multiplies the two evaluations. Norms of products are therefore controlled sharply rather than loosely. In this power-of-two case the two geometries differ only by scale. The vectors \((\alpha_1^j, \ldots, \alpha_n^j)\) for \(j = 0, \ldots, n-1\) are mutually orthogonal of length \(\sqrt{n}\), so the canonical embedding multiplies every coefficient-vector length by exactly \(\sqrt{n}\). Other cyclotomic moduli do not enjoy this orthogonality, and there only the canonical embedding gives the sharp control.

The canonical embedding is a device for analysis, and ring elements are never actually computed as tuples of complex numbers. Its role is to give the reduction a geometry in which the error distribution and the shortness of solutions can be measured cleanly, and in cyclotomic rings that geometry is especially regular.

Module Lattices and ML-KEM

The ring construction buys efficiency at the cost of a stronger hardness assumption. Security now rests on ideal lattices rather than arbitrary ones. The key-encapsulation standard described below declines both the single large ring that would concentrate all trust in one ring's structure and the unstructured coordinates that would forfeit the efficiency. Instead, it interpolates between them, working with vectors of ring elements that form a module. This middle path is what reaches the algorithm standardized in 2024.

From Rings to Modules

The interpolation is a single generalization of everything above. Where Ring-LWE fixed a secret ring element \(s \in R_q\) and published noisy products \(a \cdot s + e\), its module form fixes a secret vector of ring elements \(\mathbf{s} \in R_q^k\) and publishes noisy inner products \[ b = \langle \mathbf{a}, \mathbf{s} \rangle + e = a_1 s_1 + \cdots + a_k s_k + e \bmod q, \] where \(\mathbf{a} \in R_q^k\) is a uniformly random vector of ring elements and the inner product is taken in \(R_q\). This is module learning with errors, or Module-LWE.

The rank \(k\) is a tuning dial between the two problems already built. At \(k = 1\) the module problem is exactly Ring-LWE, with a single ring element. If the ring is taken to be \(\mathbb{Z}\) itself, of degree one and with no polynomial structure, the problem collapses back to coordinate learning with errors. Every learning-with-errors problem met so far is one setting of that dial.

The hardness guarantee generalizes in step. Just as Ring-LWE was tied to shortest-vector problems on ideal lattices, Module-LWE is at least as hard as approximating worst-case lattice problems on module lattices, the lattices corresponding to \(R\)-submodules of \(R^k\). These sit strictly between the two earlier worlds: more structured than the arbitrary lattices behind coordinate learning with errors, less structured than the single ideal lattices behind Ring-LWE. This intermediate position, and the reason a standard would deliberately seek it, is the substance of the rank parameter.

ML-KEM

The key-encapsulation mechanism standardized in 2024 as the primary post-quantum replacement for classical key exchange, named ML-KEM (module-lattice-based key-encapsulation mechanism), is built directly on Module-LWE. Its base ring is the cyclotomic \(R_q = \mathbb{Z}_q[x]/(x^{256} + 1)\) with prime modulus \(q = 3329\), fixed across all security levels. The rank \(k\) is the single parameter that varies, and it takes the values \(k = 2, 3, 4\) to give the three standardized strengths. The degree \(256\) and the prime \(3329\) are chosen together so that the ring supports the fast transform that makes multiplication near-linear, the point promised above and settled now.

Because \(q \equiv 1 \pmod{256}\) but not modulo \(512\), the field \(\mathbb{Z}_q\) contains primitive \(256\)-th roots of unity but no primitive \(512\)-th root. The roots of \(x^{256} + 1\) are primitive \(512\)-th roots of unity, so the polynomial does not split into linear factors. It factors modulo \(q\) into \(128\) quadratic polynomials rather than remaining whole. A number-theoretic transform, the finite-field analogue of the discrete Fourier transform, maps a ring element to its residues modulo those \(128\) factors, in which multiplication becomes a component-wise product of low-degree pieces. The transform and its inverse run in \(O(n \log n)\) time, replacing the \(O(n^2)\) cost of a direct convolution.

The construction proceeds in two stages, following the pattern the classical encryption pages established. First a public-key encryption scheme is built directly from Module-LWE. The public key is a Module-LWE instance, encryption hides a message by adding it to a fresh noisy combination of that instance, and decryption removes the noise using the secret. Because the noise is only bounded, not eliminated, decryption carries a small probability of failure. Such failures are intrinsic to the lattice construction, and the parameters are chosen to make their probability astronomically small.

This scheme is secure against passive eavesdroppers, but not against an adversary who submits crafted ciphertexts and observes the responses. The second stage closes that gap with the Fujisaki-Okamoto transform, a generic procedure that upgrades a passively secure encryption scheme into a key-encapsulation mechanism secure against adaptive chosen-ciphertext attacks. The transform derandomizes encryption and forces the recipient to re-encrypt and verify, so a malformed ciphertext is detected rather than answered. The result is ML-KEM.

Where the Track Arrives

The cryptography track now completes the arc it has been building toward. The classical schemes fell to a quantum algorithm. The geometry and complexity pages then rebuilt hardness from worst-case lattice problems, and the two preceding pages turned that hardness into a hash and an encryption, conjecturally quantum-resistant but too large to deploy. This page supplied the missing efficiency by moving the whole construction into a polynomial ring, where a single element carries a vector's worth of data and multiplication runs in near-linear time. The price of that speed is a hardness assumption narrowed from arbitrary lattices to the ideal and module lattices that inherit the ring's symmetry. The endpoint is ML-KEM, resting on a chain of reductions that reaches all the way back to the worst-case geometry the earliest pages measured.