6.7 Ring-LWE and Module-LWE

Ring-LWE is Learning With Errors where the secret, the noise and the public values are polynomials in a ring such as $\mathbb{Z}_q[X]/(X^n+1)$. One random polynomial takes the place of a whole $n \times n$ matrix, so keys shrink from about $n^2$ numbers to $n$. Module-LWE sits in between: it uses a small $k \times k$ matrix of such polynomials. ML-KEM (Kyber) and ML-DSA (Dilithium) are both built on Module-LWE.

Plain LWE and its size problem

In Learning With Errors you are given a random matrix $A \in \mathbb{Z}_q^{m \times n}$ and a vector $b = As + e \bmod q$, where $s$ is secret and $e$ is a vector of small errors. Recovering $s$, or even telling $b$ apart from uniform, is believed hard. The cost is size: with $m = n$, the matrix alone holds $n^2$ numbers. At the dimension used by ML-KEM-768, $n = 768$, that is 589,824 entries, and every multiplication by $A$ takes about as many operations.

What is Ring-LWE?

Ring-LWE replaces vectors of integers with polynomials and the matrix with a single polynomial. Work in the ring

whose elements are polynomials of degree below $n$ with coefficients mod $q$. Multiplication is ordinary polynomial multiplication followed by the rule $X^n = -1$. The ring notation is summarised in 8.4 Rings and polynomials.

One polynomial is a structured matrix

Multiplying by a fixed $a$ is a linear map on the coefficient vector of $s$, so it has a matrix. Column $j$ of that matrix holds the coefficients of $a \cdot X^j$: the coefficients of $a$ shifted down by $j$ places, with every coefficient that wraps around negated. Take $n = 4$, $q = 17$ and $a = 3 + X + 4X^2 + X^3$:

Four numbers determine all sixteen entries. With the small secret $s = 1 - X^2 + X^3$, coefficient vector $(1, 0, -1, 1)$, both $a \cdot s$ and $M_a s$ give $(6, 15, 0, 3)$ mod 17. Adding the error $e = (1, -1, 0, 1)$ gives the public value $b = (7, 14, 0, 4)$. Seen as a lattice problem, a Ring-LWE sample is an LWE sample whose matrix happens to be negacyclic.

The saving goes beyond storage. Because $q = 3329$ is chosen so that $X^{256} + 1$ splits mod $q$, products in $R_q$ can be computed with the number theoretic transform in $O(n \log n)$ operations instead of $O(n^2)$.

How hard is Ring-LWE?

Lyubashevsky, Peikert and Regev (2010) showed that, for rings such as $\mathbb{Z}[X]/(X^n+1)$ with $n$ a power of two, solving Ring-LWE on average is at least as hard as solving approximate shortest-vector problems on ideal lattices in the worst case, using a quantum reduction. Ideal lattices are a special class, so this is a weaker foundation than the reduction for plain LWE, which starts from arbitrary lattices. In practice, the best known attacks on Ring-LWE at cryptographic parameters are the same lattice-reduction attacks used against plain LWE of the same dimension.

What is Module-LWE?

Module-LWE keeps the polynomial ring but brings back a small matrix. The secret is a vector of $k$ polynomials and the public matrix is $k \times k$ polynomials.

The two earlier problems are special cases. With $k = 1$ the matrix is a single polynomial: that is Ring-LWE. With $n = 1$ the ring is just $\mathbb{Z}_q$ and $A$ is an ordinary integer matrix: that is plain LWE. Langlois and Stehlé (2015) gave worst-case to average-case reductions for Module-LWE from problems on module lattices, which contain the ideal lattices of Ring-LWE as the rank-one case.

A toy Module-LWE sample in Python

The code below builds one sample with $n = 8$, $k = 2$ and $q = 3329$, using plain Python. It draws small values uniformly from $\{-2, \dots, 2\}$ for simplicity; ML-KEM uses a centred binomial distribution instead.

import random

n, q, k, eta = 8, 3329, 2, 2          # toy sizes; ML-KEM uses n = 256
rng = random.Random(1)

def polymul(a, b):
    """Multiply in Z_q[X]/(X^n + 1): wrap-around terms change sign."""
    c = [0] * n
    for i, ai in enumerate(a):
        for j, bj in enumerate(b):
            if i + j < n:
                c[i + j] = (c[i + j] + ai * bj) % q
            else:
                c[i + j - n] = (c[i + j - n] - ai * bj) % q
    return c

def add(a, b):
    return [(x + y) % q for x, y in zip(a, b)]

def uniform():
    return [rng.randrange(q) for _ in range(n)]

def small():
    return [rng.randint(-eta, eta) % q for _ in range(n)]

A = [[uniform() for _ in range(k)] for _ in range(k)]  # k x k matrix of polynomials
s = [small() for _ in range(k)]                         # secret: k small polynomials
e = [small() for _ in range(k)]                         # error: k small polynomials

b = []
for i in range(k):
    row = e[i]
    for j in range(k):
        row = add(row, polymul(A[i][j], s[j]))
    b.append(row)

centered = lambda p: [x - q if x > q // 2 else x for x in p]
print("s[0] =", centered(s[0]))
print("b[0] =", b[0])
print("numbers in A:", k * k * n, "  plain LWE would need:", (k * n) ** 2)

s[0] = [0, -2, -2, -2, 2, -2, 1, -1]
b[0] = [1055, 8, 2628, 307, 706, 570, 860, 3310]
numbers in A: 32   plain LWE would need: 256

The secret stays small while $b$ looks like random numbers mod 3329. At ML-KEM-768 sizes, $k = 3$ and $n = 256$, the matrix has 2,304 coefficients instead of 589,824, and ML-KEM does not even store those: it regenerates $A$ from a 32-byte seed.

Ring-LWE vs Module-LWE vs plain LWE

Why ML-KEM and ML-DSA use Module-LWE

Module-LWE gives most of the size and speed of Ring-LWE while keeping one ring for every security level. ML-KEM (FIPS 203) fixes $n = 256$ and $q = 3329$ and sets $k = 2, 3, 4$ for ML-KEM-512, -768 and -1024. The same NTT code, the same polynomial arithmetic and the same hardware serve all three. ML-DSA (FIPS 204) does the same with $n = 256$ and $q = 8{,}380{,}417$, using a $k \times \ell$ matrix of size $4 \times 4$, $6 \times 5$ and $8 \times 7$ for its three parameter sets. There the security relies on Module-LWE for the keys and on Module-SIS for the signatures.

Does the ring structure make it weaker?

Structure is a risk in principle, and it is the main reason the reductions are stated for ideal or module lattices rather than all lattices. Some algebraic attacks do exist: for example, there are quantum algorithms that find unusually short vectors in principal ideal lattices better than general lattice reduction can. None of these translate into a practical attack on Ring-LWE or Module-LWE at the parameters of ML-KEM or ML-DSA, whose security estimates come from the same primal and dual lattice attacks used against plain LWE. The power-of-two cyclotomic ring $\mathbb{Z}[X]/(X^n+1)$ is chosen because it is fast, well studied and has no known weakness for these problems. Module-LWE adds a margin over Ring-LWE because the lattice has less algebraic symmetry.

Common mistakes

• Reducing mod $X^n - 1$ instead of $X^n + 1$. The wrapped coefficient must change sign. With $X^n - 1$ you get a cyclic ring whose structure is weaker and whose NTT differs.
• Counting Module-LWE dimension as $k$. The lattice an attacker reduces has dimension $k n$, which is 768 for ML-KEM-768.
• Treating Ring-LWE as proved as hard as plain LWE. Its reduction starts from ideal lattices, a narrower class. The practical evidence is that no better attack is known.
• Sampling the secret uniformly mod $q$. Secret and error must be small; a uniform secret breaks decryption correctness and changes the problem.

Further reading

V. Lyubashevsky, C. Peikert and O. Regev, On Ideal Lattices and Learning with Errors over Rings, Eurocrypt 2010. A. Langlois and D. Stehlé, Worst-case to Average-case Reductions for Module Lattices, Designs, Codes and Cryptography, 2015. NIST FIPS 203 (ML-KEM) and FIPS 204 (ML-DSA), 2024, for the exact parameter sets. The first two references are cited from memory. See also the q-ary lattices guide for the lattice behind LWE samples.