Chapter 9: Ring-LWE and Module-LWE

Ring-LWE is the ring-structured analogue of LWE. The secret, the public element, and the error are all polynomials in the ring $R_q = \mathbb{Z}_q[x]/(x^n + 1)$, with $n$ a power of two. A Ring-LWE sample is a pair $(a, b)$ of ring elements with $b = a \cdot s + e$. The secret $s$ is a polynomial drawn uniformly from $R_q$, and the error $e$ has small coefficients from a short distribution (Lyubashevsky et al., 2010). A flat LWE instance at the same dimension stores an $m \times n$ matrix of field elements. Ring-LWE stores one polynomial $a$ instead. The implicit $n \times n$ negacyclic circulant that multiplication by $a$ realizes is never written down.

Module-LWE is the same idea at rank $k$. The secret is a vector in $R_q^k$, the public data is an $m \times k$ matrix of ring elements, and the error is a vector in $R_q^m$. At $k = 1$, Module-LWE coincides with Ring-LWE. At $n = 1$, the ring collapses to $\mathbb{Z}_q$ and Module-LWE coincides with flat LWE. ML-KEM uses Module-LWE at module rank $k \in \{2, 3, 4\}$ over the single ring $\mathbb{Z}_{3329}[x]/(x^{256} + 1)$ for its three security levels (National Institute of Standards and Technology, 2024). The number theoretic transform makes polynomial multiplication in $R_q$ run in $\Theta(n \log n)$ time at the parameters practical schemes pick, under a simple arithmetic condition on $q$.

The ring $R_q$ and its negacyclic multiplication

Fix a prime $q$ and an integer $n$ that is a power of two. The ring

$$R_q = \mathbb{Z}_q[x] / (x^n + 1)$$

consists of equivalence classes of polynomials in $\mathbb{Z}_q[x]$ modulo the polynomial $x^n + 1$ (Lang, 2002). A canonical representative is a polynomial of degree strictly less than $n$. We write it as a length-$n$ coefficient vector $(f_0, f_1, \ldots, f_{n-1})$ with $f_i \in \mathbb{Z}_q$. Addition is coefficient-wise modulo $q$: $(f + g)_i = f_i + g_i \bmod q$. Multiplication starts in $\mathbb{Z}[x]$ and then uses two reductions. The polynomial product $f \cdot g$ has degree at most $2n - 2$. Every coefficient at position $n + j$ with $j \geq 0$ is moved to position $j$ with a sign flip. The sign flip comes from $x^n + 1 \equiv 0$ in $R_q$, which rearranges to $x^n \equiv -1$. After the fold, every coefficient is reduced modulo $q$. The schoolbook loop in the code block below forms each of the $n^2$ products $f_i g_j$ once, and the fold only adds or subtracts products already formed, so this method multiplies two elements of $R_q$ with $n^2$ coefficient multiplications. That counts arithmetic operations on coefficients, not bit operations.

The sign flip is the difference between $R_q$ and the cyclic ring $\mathbb{Z}_q[x]/(x^n - 1)$. The cyclic modulus $x^n - 1$ always carries the visible root $x = 1$, because $x^n - 1 = (x - 1)(x^{n-1} + \cdots + 1)$. An attacker can use that root. Evaluation at $x = 1$ maps the cyclic ring onto $\mathbb{Z}_q$ and respects addition and multiplication. A Ring-LWE sample $b = a \cdot s + e$ over that ring therefore gives $b(1) = a(1)\,s(1) + e(1)$, one equation in the single unknown $s(1)$ with a small error. Trying all $q$ values of $s(1)$ against such equations can tell the samples from uniform ones, and the sampling section below runs that attack.

The negacyclic modulus $x^n + 1$ avoids the factor $x - 1$. It may still factor over $\mathbb{Z}_q$, and when $2n \mid q - 1$ it splits completely into $n$ distinct linear factors. That full factorization is exactly what the NTT exploits, in the “The number theoretic transform” section below.

One hand example fixes the mechanics. Take $n = 4$, $q = 17$, $f = 1 + 2x + 3x^2 + 4x^3$, and $g = 5 + 6x$. The product in $\mathbb{Z}[x]$ is

$$f \cdot g = 5 + 16 x + 27 x^2 + 38 x^3 + 24 x^4 \in \mathbb{Z}[x].$$

The single term above degree $n - 1 = 3$ is $24 x^4$. Applying $x^4 \equiv -1$ subtracts $24$ from the constant term and leaves the higher terms alone. The folded polynomial is $(-19) + 16 x + 27 x^2 + 38 x^3$. Reducing each coefficient modulo $17$ gives the final answer in $R_{17}$:

$$f \cdot g \equiv 15 + 16 x + 10 x^2 + 4 x^3 \pmod{x^4 + 1, 17}.$$

The constant term is $-19 \equiv 15 \pmod{17}$. The other three are $16$, $27 - 17 = 10$, and $38 - 34 = 4$. The inline code block below implements schoolbook negacyclic multiplication in numpy. It prints the same four coefficients that the hand calculation produced.

import numpy as np

def ring_mul_naive(f, g, q):
    n = len(f)
    h = np.zeros(n, dtype=np.int64)
    for i in range(n):
        for j in range(n):
            k = i + j
            if k < n:
                h[k] += f[i] * g[j]
            else:
                # x^n = -1 wraps the tail into the head with a sign flip
                h[k - n] -= f[i] * g[j]
    return h % q

f = np.array([1, 2, 3, 4], dtype=np.int64)
g = np.array([5, 6, 0, 0], dtype=np.int64)
h = ring_mul_naive(f, g, 17)
print("f * g in R_17 =", h.tolist())
# ==> f * g in R_17 = [15, 16, 10, 4]

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch09/, one file per block. Appendix C covers the clone and the environment they run on.

The package under solutions/ch09-ring-lwe/ ships the same function, ring_mul_naive, in ring_lwe.ring. It also ships a vector-add helper, NTT routines for the $\Theta(n \log n)$ path, and Ring-LWE and Module-LWE sampling. The tests under tests/ch09/ verify the hand example above, negacyclic wraparound on single-term inputs, and commutativity, associativity, and distributivity on random seeds.

Ring-LWE and Module-LWE

A Ring-LWE instance is specified by a parameter tuple $(n, q, m, \chi_R)$. Here $n$ is the ring degree, $q$ is the prime modulus, $m$ is the number of samples, and $\chi_R$ is a short error distribution over ring elements (Lyubashevsky et al., 2010). In the toy code below, “short” means coefficient-wise small: $\chi_R$ draws each coefficient uniformly from $\{-B, -B+1, \ldots, B\}$ for a nonnegative integer noise bound $B$. ML-KEM specifies its small ring elements through a centered binomial distribution $D_\eta(R_q)$, parameterized by an integer $\eta \in \{2, 3\}$ (National Institute of Standards and Technology, 2024). Chapter 8’s note “Which error distribution” sets both beside a Gaussian, the error of Regev’s reduction, and says why the three are not interchangeable inside a reduction. Over a ring there is one more difference: the reductions measure their errors in coordinates other than the coefficients this chapter computes with, as the hardness section below explains.

Search Ring-LWE. Fix $(n, q, m, \chi_R)$ and draw $a$ uniform in $R_q$, $s$ uniform in $R_q$, and $e$ from $\chi_R$. Set $b = a \cdot s + e$ in $R_q$. The search problem gives the solver $m$ independent samples $(a_i, b_i)$ that all share the same secret $s$. The task is to recover $s$ (Lyubashevsky et al., 2010). The solver sees the $m$ pairs and the parameters. The secret and the errors are hidden. At $m = 1$, the advantage is the probability of recovering $s$ from one sample. At larger $m$, the solver gets independent algebraic relations on the same secret.

Decisional Ring-LWE. The decisional problem presents $m$ samples $(a_i, b_i)$ drawn from one of two distributions with equal probability. On the Ring-LWE side, each $b_i = a_i \cdot s + e_i$ for a fixed secret $s$ and independent $e_i$ from $\chi_R$. On the uniform side, each $b_i$ is drawn independently and uniformly from $R_q$. The solver must decide which (Lyubashevsky et al., 2010). Decisional Ring-LWE is the distinguishing game that IND-CPA proofs for Ring-LWE schemes rest on: a proof like Chapter 10’s for Regev’s scheme turns an adversary that beats the IND-CPA game into a distinguisher for the underlying problem. Search and decisional Ring-LWE are equivalent up to polynomial factors for a prime $q$ bounded by a polynomial in $n$ with $q \equiv 1 \pmod{2n}$, and for the error family the reduction is stated for. The hardness section below gives both conditions (Lyubashevsky et al., 2010, sec. 4).

The definitions above use a uniform secret $s \in R_q$, the cleanest textbook form. Many practical schemes including ML-KEM use small secrets as well as small errors (National Institute of Standards and Technology, 2024), and the proof and parameter-estimation story for those small-secret variants is not identical to the uniform-secret one. Chapter 11 picks up the small-secret form when assembling ML-KEM.

The compression from flat LWE to Ring-LWE can be stated as a structural identity. Fix $n$ and consider one sample $(a, b) \in R_q \times R_q$ with $b = a \cdot s + e$. Write the coefficients of $a$ as $(a_0, \ldots, a_{n-1})$ and the coefficients of $s$ as a column vector $\mathbf{s} \in \mathbb{Z}_q^n$. The coefficients of the ring product $a \cdot s$ are the entries of a matrix-vector product $M_a \mathbf{s}$, where $M_a \in \mathbb{Z}_q^{n \times n}$ is a negacyclic circulant determined by $a$.

The matrix $M_a$ is built column by column. The first column is $(a_0, a_1, \ldots, a_{n-1})^\top$, which is the coefficient vector of $a$. Each next column is the previous one rotated down by one position, with the element that wraps off the bottom reintroduced at the top with a sign flip. The sign flip encodes $x^n \equiv -1$: when a coefficient is shifted off the bottom, past degree $n - 1$, it comes back negated at the top. The last column is $(-a_1, -a_2, \ldots, -a_{n-1}, a_0)^\top$.

The matrix $M_a$ has $n^2$ entries, but only $n$ of them are free. The other $n^2 - n$ are determined by the first column. One element $a \in R_q$ therefore replaces the full $n \times n$ matrix in the flat-LWE presentation.

The compression factor grows with $n$. Flat LWE at secret dimension $n$ and sample count $m$ stores an $m \times n$ matrix, which is $mn$ field elements of public data. Ring-LWE at the same $n$ and $m$ stores $m$ ring elements, which is also $mn$ field elements. The savings appear when compared against the algebraic yield of each sample. Each ring element $a_i \in R_q$ carries $n$ linear equations on the coefficients of $s$. One Ring-LWE sample is therefore comparable to $n$ rows of a flat LWE matrix. The public data per linear equation drops from $n$ field elements in flat LWE to one field element in Ring-LWE. That factor-of-$n$ compression is the practical appeal of the ring form.

The price of the compression is structure: the $n$ relations from one Ring-LWE sample are not independent flat-LWE rows, but correlated through the negacyclic-circulant form of $M_a$. Ring-LWE is flat LWE restricted to a special algebraic family of matrices, not flat LWE with fewer bytes. The compression makes the matrix short to describe, but an ML-KEM encapsulation key does not carry the matrix at all. It carries a 32-byte seed from which the matrix is regenerated, beside two, three or four ring elements of $384$ bytes each (256 coefficients of 12 bits). That makes $800$ bytes for ML-KEM-512, $1184$ bytes for ML-KEM-768, and $1568$ bytes for ML-KEM-1024 (National Institute of Standards and Technology, 2024).

Module-LWE generalizes Ring-LWE from one ring element to a rank-$k$ vector. A Module-LWE instance is specified by a parameter tuple $(n, q, k, m, \chi_R)$, where $k$ is the module rank. Draw $\mathbf{A} \in R_q^{m \times k}$ uniform, $\mathbf{s} \in R_q^k$ uniform, and $\mathbf{e} \in R_q^m$ with each entry from $\chi_R$. Set $\mathbf{b} = \mathbf{A} \mathbf{s} + \mathbf{e}$ in $R_q^m$. The search problem is to recover $\mathbf{s}$ from $(\mathbf{A}, \mathbf{b})$. The decisional version distinguishes $(\mathbf{A}, \mathbf{b})$ from $(\mathbf{A}, \mathbf{u})$ with $\mathbf{u}$ uniform in $R_q^m$ (Langlois & Stehlé, 2015).

Two collapse identities place Module-LWE between the two endpoints. At $k = 1$, the matrix $\mathbf{A}$ degenerates to a column of ring elements. Each row is then one Ring-LWE sample sharing the same secret $s \in R_q$. At $n = 1$, the ring $R_q$ degenerates to $\mathbb{Z}_q$ via the explicit isomorphism $\mathbb{Z}_q[x]/(x + 1) \cong \mathbb{Z}_q$. A residue class modulo $x + 1$ is determined by its value at $x = -1$, which is a single field element. Module-LWE at $n = 1$ is flat LWE at secret dimension $k$. Between the two endpoints, Module-LWE with $k \geq 2$ and $n \geq 2$ carries both ring structure and module structure.

A compact comparison of the three families on public data size, secret shape, and underlying hardness is:

Family	Coefficients in $\mathbf{A}$	Secret	Worst-case hardness source
Flat LWE	$m n$ field elements	$\mathbb{Z}_q^n$	GapSVP and SIVP on general lattices (Regev, 2009)
Ring-LWE	$m n$ field elements	one polynomial in $R_q$	ideal-lattice problems in $\mathbb{Z}[\zeta_{2n}]$ (Lyubashevsky et al., 2010)
Module-LWE	$m k n$ field elements	$R_q^k$	module-lattice problems such as Mod-SIVP at rank $k$ (Langlois & Stehlé, 2015)

Those figures count the coefficients of $\mathbf{A}$ alone, not the full public sample $(\mathbf{A}, \mathbf{b})$. Adding $\mathbf{b}$ gives $m(n+1)$ field elements for flat LWE, $2 m n$ for Ring-LWE at $m$ samples, and $m(k+1)n$ for Module-LWE. The gap between the families is not in bytes but in the algebraic yield per sample. Each flat LWE row is one linear relation on the secret. Each Ring-LWE sample is $n$ linear relations, one per coefficient of the ring product. At equal $\mathbf{A}$ storage that is $n$ times as many constraints. At equal total public storage the ratio is $(n+1)/2$ instead, because Ring-LWE spends half its bytes on $\mathbf{b}$ where flat LWE spends one part in $n+1$. Module-LWE interpolates: each row of $\mathbf{A}$ pairs with one entry of $\mathbf{b}$ to give $n$ scalar relations, and those $n$ relations couple all $k$ ring-valued secret components rather than constraining each of them separately.

The number theoretic transform

The schoolbook multiplication in $R_q$ costs $\Theta(n^2)$ integer multiplications per ring product. At toy parameters this is invisible. At ML-KEM’s $n = 256$, and across the many ring products inside the module-matrix arithmetic, this is why the NTT is part of the design rather than a cosmetic optimization (National Institute of Standards and Technology, 2024). The number theoretic transform replaces the $\Theta(n^2)$ convolution with three $\Theta(n \log n)$ transforms and an $\Theta(n)$ pointwise multiplication. The replacement holds when a single arithmetic condition on $q$ is satisfied.

The condition is that $\mathbb{Z}_q$ contains a primitive $2n$-th root of unity $\psi$. A primitive $2n$-th root is a field element of multiplicative order exactly $2n$. That is: $\psi^{2n} \equiv 1 \pmod q$, and $\psi^d \not\equiv 1 \pmod q$ for every proper divisor $d$ of $2n$. The multiplicative group $\mathbb{Z}_q^\times$ is cyclic of order $q - 1$. An element of order $2n$ exists if and only if $2n$ divides $q - 1$. At $(n, q) = (4, 17)$ this holds because $q - 1 = 16 = 2 \cdot 2n$. At ML-KEM’s $(n, q) = (256, 3329)$ the condition fails: $q - 1 = 3328 = 256 \cdot 13$, and $2n = 512$ does not divide $3328$. ML-KEM uses a partial NTT that Chapter 11 develops. It works around the failure by using a primitive $256$-th root and stopping the factorization one level early.

Negacyclic factorization. When $2n \mid q - 1$, the polynomial $x^{2n} - 1$ splits into $2n$ distinct linear factors over $\mathbb{Z}_q$:

$$x^{2n} - 1 = \prod_{i=0}^{2n - 1} (x - \psi^i).$$

The factor $x^n - 1$ carries the even powers: $x^n - 1 = \prod_{i=0}^{n-1}(x - \psi^{2i})$. The factor $x^n + 1$ carries the odd powers:

$$x^n + 1 = \prod_{i=0}^{n-1} \left( x - \psi^{2i+1} \right).$$

This is the defining identity for the ring $R_q$. The modulus $x^n + 1$ is a product of $n$ distinct linear factors over $\mathbb{Z}_q$. The Chinese remainder theorem then gives a ring isomorphism

$$R_q \;\cong\; \prod_{i=0}^{n-1} \mathbb{Z}_q[x] / (x - \psi^{2i+1}) \;\cong\; \mathbb{Z}_q^n.$$

Each factor on the left is a copy of $\mathbb{Z}_q$. The identification is: reducing $\mathbb{Z}_q[x]$ modulo a linear polynomial $x - c$ evaluates at $x = c$ (Lyubashevsky et al., 2010). The explicit map from left to right is evaluation at the $n$ odd powers of $\psi$. A polynomial $f(x) \in R_q$ goes to the tuple $(f(\psi), f(\psi^3), \ldots, f(\psi^{2n-1}))$. The map is a ring homomorphism. Ring multiplication on the left becomes coordinate-wise multiplication on the right.

The NTT as an evaluation map. The negacyclic number theoretic transform is this CRT isomorphism written as a matrix. Fix $n$, $q$, and a primitive $2n$-th root $\psi$. The NTT of a coefficient vector $(f_0, \ldots, f_{n-1})$ is the length-$n$ vector $(\hat{f}_0, \ldots, \hat{f}_{n-1})$ defined by

$$\hat{f}_k = \sum_{i=0}^{n-1} f_i \cdot \psi^{i(2k+1)} \pmod q,$$

for $k = 0, 1, \ldots, n-1$. The $k$-th entry is exactly $f(\psi^{2k+1})$. Because the isomorphism is a ring homomorphism, the product $f \cdot g$ in $R_q$ satisfies $\widehat{f \cdot g}_k = \hat{f}_k \cdot \hat{g}_k$ pointwise over $k$.

The inverse transform. The CRT isomorphism has an explicit inverse from an orthogonality relation. Fix $i$ and $j$ in $\{0, 1, \ldots, n-1\}$ and compute

$$\sum_{k=0}^{n-1} \psi^{(i - j)(2k + 1)}.$$

Pull the $\psi^{(i - j)}$ factor out of the sum. What remains is $\sum_{k=0}^{n-1} \omega^{(i-j) k}$, where $\omega = \psi^2$ is a primitive $n$-th root of unity. The geometric-series identity for roots of unity gives $n$ when $i \equiv j \pmod n$ and $0$ otherwise. For $0 \leq i, j < n$ this collapses to $n \cdot [i = j]$. The original sum is then $n$ when $i = j$ and $0$ otherwise. Rearranging, the inverse NTT is

$$f_j = n^{-1} \sum_{k=0}^{n-1} \hat{f}_k \cdot \psi^{-j(2k+1)} \pmod q,$$

for $j = 0, 1, \ldots, n-1$. The inverse uses the same sum structure as the forward transform. It uses $\psi^{-1}$ in place of $\psi$ and a final multiplication by $n^{-1}$. Both $\psi^{-1}$ and $n^{-1}$ exist in $\mathbb{Z}_q$ because $q$ is prime.

At $(n, q) = (4, 17)$, a primitive $8$-th root of unity is $\psi = 2$. The verification is a chain of exponentiations. We have $2^1 = 2$, $2^2 = 4$, $2^4 = 16 \equiv -1$, and $2^8 = (-1)^2 = 1$. So $\psi = 2$ has order exactly $8$. At $(n, q) = (8, 17)$, a primitive $16$-th root is $\psi = 3$. The check is $3^8 \equiv -1 \pmod{17}$, from which $3^{16} \equiv 1$ and no smaller divisor of $16$ gives $1$. The package helper primitive_2n_root(n, q) searches $\psi \in \{2, 3, \ldots, q-1\}$ until it finds an element of order $2n$. It caches the result by $(n, q)$.

Figure 9.1 shows the negacyclic factorization at $n = 4$, $q = 17$. The polynomial $x^4 + 1$ factors over $\mathbb{Z}_{17}$ into four distinct linear factors $(x - \psi)(x - \psi^3)(x - \psi^5)(x - \psi^7)$, where $\psi = 2$ is a primitive $8$-th root of unity. The NTT evaluates a polynomial $f \in R_{17}$ at these four points. It delivers the tuple $(f(\psi), f(\psi^3), f(\psi^5), f(\psi^7))$ as the image of $f$ in $\mathbb{Z}_{17}^4$. Pointwise multiplication in $\mathbb{Z}_{17}^4$ corresponds to multiplication in $R_{17}$. The inverse NTT recovers the coefficient vector from the evaluations.

Figure 9.1. The negacyclic factorization of $x^4 + 1$ over $\mathbb{Z}_{17}$ into four linear factors at the odd powers of the primitive $8$-th root of unity $\psi = 2$. The NTT at $(n, q) = (4, 17)$ is the Chinese remainder theorem isomorphism $R_{17} \cong \mathbb{Z}_{17}^4$, realized by evaluating a polynomial at $\{2, 8, 15, 9\}$.

A tiny NTT, end to end. The inline code block below implements the negacyclic NTT from the direct definition at $(n, q, \psi) = (4, 17, 2)$. It transforms $f = 1 + 2x + 3x^2 + 4x^3$ and $g = 5 + 6x$, multiplies pointwise, inverse-transforms, and prints the result. The output matches the schoolbook product $15 + 16x + 10x^2 + 4x^3$ computed by hand earlier.

import numpy as np

n, q, psi = 4, 17, 2
psi_inv = pow(psi, -1, q)
n_inv = pow(n, -1, q)

def ntt_forward(f):
    fhat = np.zeros(n, dtype=np.int64)
    for k in range(n):
        acc = 0
        for i in range(n):
            acc += int(f[i]) * pow(psi, i * (2 * k + 1), q)
        fhat[k] = acc % q
    return fhat

def ntt_inverse(fhat):
    f = np.zeros(n, dtype=np.int64)
    for j in range(n):
        acc = 0
        for k in range(n):
            acc += int(fhat[k]) * pow(psi_inv, j * (2 * k + 1), q)
        f[j] = (n_inv * acc) % q
    return f

f = np.array([1, 2, 3, 4], dtype=np.int64)
g = np.array([5, 6, 0, 0], dtype=np.int64)
fhat = ntt_forward(f)
ghat = ntt_forward(g)
hhat = (fhat * ghat) % q
h = ntt_inverse(hhat)
print("fhat =", fhat.tolist())
# ==> fhat = [15, 13, 11, 16]
print("ghat =", ghat.tolist())
# ==> ghat = [0, 2, 10, 8]
print("f * g in R_17 via NTT =", h.tolist())
# ==> f * g in R_17 via NTT = [15, 16, 10, 4]

Interactive demo

An interactive version of this transform is at the negacyclic-NTT butterfly demo. Step the pre-twist and the Cooley-Tukey butterfly stages at $(n, q, \psi) = (4, 17, 2)$. Watch the coefficient slots and the active butterfly pair update, then see the pointwise product and inverse NTT rebuild the schoolbook product $[15, 16, 10, 4]$.

The direct-definition form runs in $\Theta(n^2)$ operations, same as the schoolbook convolution. The asymptotic speedup comes from an iterative Cooley-Tukey decomposition layered with the negacyclic pre-twist. At each layer, the $n$-point transform splits into two $n/2$-point transforms plus a linear combination. The input is pre-multiplied by the appropriate powers of $\psi$ before the discrete Fourier transform layer. The pre-twist makes the final evaluation points the odd powers of $\psi$ rather than the even powers. Fast implementations of this full transform exist for the moduli that allow it, those with $q \equiv 1 \pmod{2n}$. Seiler’s vectorized ones, for NewHope’s $q = 12289$ and Kyber’s earlier $q = 7681$, do without the separate pre-twist and split $x^n + 1$ directly (Sections 2 and 2.1 in Seiler, 2018). So does Longa and Naehrig’s, whose butterflies absorb the powers of $\psi$ and which adds a faster modular reduction for primes of that special form (Longa & Naehrig, 2016). ML-KEM’s $q = 3329$ does not allow the full transform. Since $3328 = 2^8 \cdot 13$, $\mathbb{Z}_{3329}$ has no primitive $512$-th root of unity, and ML-KEM’s transform stops at $128$ quadratic factors (National Institute of Standards and Technology, 2024, sec. 4.3). The Kyber team’s reference and AVX2 implementations avoid timing leakage in the modular reductions by using Montgomery and Barrett reduction (Avanzi et al., 2021, sec. 4.5.2). Chapter 11 walks that transform at ML-KEM scale when it is time to assemble the KEM.

The agreement between ring_mul_ntt and ring_mul_naive is an algebraic identity, and what the suite in tests/ch09/test_ntt.py shows is a sample of it. At $(n, q) = (4, 17)$ and $(n, q) = (8, 17)$ it draws 30 polynomial pairs, multiplies them both ways, and checks the results agree. Each parameter set uses one fixed seed for all 30 draws, 2 and 3 respectively, so this is 60 sampled products rather than an exhaustive check.

Sampling Ring-LWE and Module-LWE in Python

Fix the toy parameters $(n, q, B) = (4, 17, 1)$. The ring degree is $n = 4$, the modulus is the prime $q = 17$, and the noise bound is $B = 1$. Every error coefficient therefore lies in $\{-1, 0, 1\}$ before reduction modulo $q$. The code block below draws one Ring-LWE sample. It verifies the defining identity $b = a \cdot s + e$ in $R_q$ using the schoolbook multiplication from the first section.

import numpy as np

n, q, B = 4, 17, 1
rng = np.random.default_rng(seed=0)

def ring_mul_naive(f, g, q):
    n = len(f)
    h = np.zeros(n, dtype=np.int64)
    for i in range(n):
        for j in range(n):
            k = i + j
            if k < n:
                h[k] += f[i] * g[j]
            else:
                h[k - n] -= f[i] * g[j]
    return h % q

a = rng.integers(low=0, high=q, size=n, dtype=np.int64)
s = rng.integers(low=0, high=q, size=n, dtype=np.int64)
raw_e = rng.integers(low=-B, high=B + 1, size=n, dtype=np.int64)
e = raw_e % q
b = (ring_mul_naive(a, s, q) + e) % q

print("a =", a.tolist())
# ==> a = [14, 10, 8, 4]
print("s =", s.tolist())
# ==> s = [5, 0, 1, 0]
print("raw e =", raw_e.tolist())
# ==> raw e = [-1, 1, 0, 1]
print("b =", b.tolist())
# ==> b = [10, 13, 3, 14]

# Independent identity check. Compute the Z[x] product via numpy.convolve
# and fold the tail into the head with a sign flip (x^n = -1), yielding
# a second path to a * s in R_q that does not call ring_mul_naive.
raw_prod = np.convolve(a, s).astype(np.int64)  # length 2n - 1 = 7
folded = raw_prod[:n].copy()
# raw_prod[n:] has n-1 entries at positions n..2n-2; each subtracts into
# folded[0..n-2] under x^n = -1. The head term at position n-1 (degree
# x^{n-1}) does not wrap and stays in folded[n-1] untouched.
folded[:n - 1] -= raw_prod[n:]
expected_b = (folded + e) % q
print("independent expected b =", expected_b.tolist())
# ==> independent expected b = [10, 13, 3, 14]
print("b == expected :", (b == expected_b).all())
# ==> b == expected : True

The secret $s$ has four coefficients drawn uniformly from $\mathbb{Z}_{17}$. The ring element $a$ has the same shape. The error $e$ has four coefficients drawn from $\{-1, 0, 1\}$, with one zero entry for this seed. The final print confirms that the returned $b$ matches the formula used to build it. The function sample_ring_lwe in the ch09-ring-lwe package under solutions/ returns the full tuple $(a, s, e, b)$. Tests can then verify the identity directly.

Attacking the cyclic ring’s root. The first section noted that the cyclic modulus $x^n - 1$ has the root $x = 1$. Evaluating a polynomial at $1$ sums its coefficients. In the cyclic ring that evaluation respects addition and multiplication, because reducing a product modulo $x^n - 1$ changes it by a multiple of $x^n - 1$, which is $0$ at $x = 1$. A sample $b = a \cdot s + e$ built in that ring therefore satisfies $b(1) = a(1)\,s(1) + e(1)$ in $\mathbb{Z}_q$, with $|e(1)| \leq nB$, since $e(1)$ sums $n$ coefficients of absolute value at most $B$. An attacker tries each of the $q$ values $t$ for $s(1)$ and keeps $t$ when $b_i(1) - a_i(1)\,t$ lies within $nB$ of $0$ for every sample. The true $s(1)$ always passes.

In $R_q$ the reduction is modulo $x^n + 1$, which is $2$ at $x = 1$, so evaluation at $1$ does not respect multiplication: $x^{n-1} \cdot x = x^n = -1$ in $R_q$, while each factor evaluates to $1$. The code block below runs the test with $m = 16$ samples at the toy parameters, on both rings.

import numpy as np

n, q, B, m = 4, 17, 1, 16
rng = np.random.default_rng(seed=0)

def ring_mul(f, g, q, wrap):
    # wrap = +1: the cyclic ring, x^n = 1. wrap = -1: R_q, x^n = -1.
    n = len(f)
    h = np.zeros(n, dtype=np.int64)
    for i in range(n):
        for j in range(n):
            if i + j < n:
                h[i + j] += f[i] * g[j]
            else:
                h[i + j - n] += wrap * f[i] * g[j]
    return h % q

def draw(wrap, uniform):
    # The sampler knows s. The attacker sees only the m pairs (a, b).
    s = rng.integers(low=0, high=q, size=n, dtype=np.int64)
    pairs = []
    for _ in range(m):
        a = rng.integers(low=0, high=q, size=n, dtype=np.int64)
        if uniform:
            b = rng.integers(low=0, high=q, size=n, dtype=np.int64)
        else:
            e = rng.integers(low=-B, high=B + 1, size=n, dtype=np.int64)
            b = (ring_mul(a, s, q, wrap) + e) % q
        pairs.append((a, b))
    return pairs, int(s.sum()) % q

def survivors(pairs):
    # Evaluating at x = 1 sums coefficients. Keep each guess t for s(1)
    # whose residual b(1) - a(1) t lies within n * B of 0 on every pair.
    def short(r):
        r %= q
        return min(r, q - r) <= n * B
    return [t for t in range(q)
            if all(short(int(b.sum()) - int(a.sum()) * t)
                   for a, b in pairs)]

pairs, s1 = draw(wrap=+1, uniform=False)
print("cyclic, Ring-LWE:", survivors(pairs), "and s(1) =", s1)
# ==> cyclic, Ring-LWE: [2] and s(1) = 2
pairs, _ = draw(wrap=+1, uniform=True)
print("cyclic, uniform:", survivors(pairs))
# ==> cyclic, uniform: []
pairs, s1 = draw(wrap=-1, uniform=False)
print("R_q, Ring-LWE:", survivors(pairs), "and s(1) =", s1)
# ==> R_q, Ring-LWE: [] and s(1) = 1

On the cyclic ring one guess survives, and it is $s(1)$. On uniform samples none does, so accepting whenever a guess survives tells the two kinds of sample apart. That breaks decisional Ring-LWE over the cyclic ring at these parameters, although the attack learns only $s(1)$, one linear function of the secret, and not $s$ itself.

That separation comes from the algebra, not from the seed. A uniform $b_i$ makes each residual uniform in $\mathbb{Z}_q$, so a fixed guess passes one sample with probability $(2nB + 1)/q = 9/17$. Summed over the $q$ guesses, the chance that some guess passes all $m$ samples is at most $q\,((2nB + 1)/q)^m$: about $6.5 \times 10^{-4}$ at $m = 16$, and $0.105$ at $m = 8$. Over $x^n + 1$ the run keeps no guess, the true $s(1)$ included. That shows only that the identity fails there, not that the negacyclic toy is secure: at $n = 4$ and $q = 17$, trying all $17^4$ secrets breaks it.

Module-LWE at rank $k = 2$. ML-KEM-512 uses Module-LWE at rank $k = 2$ over its $n = 256$ ring. The toy version at $(n, q, k, m, B) = (4, 17, 2, 4, 1)$ has the same shape on a much smaller ring. The code block below samples a matrix $\mathbf{A}$ of four rows and two columns of ring elements. It also samples a secret $\mathbf{s}$ of two ring elements, an error vector $\mathbf{e}$ of four ring elements, and the target $\mathbf{b} = \mathbf{A} \mathbf{s} + \mathbf{e}$.

import numpy as np

n, q, k, m, B = 4, 17, 2, 4, 1

def ring_mul_naive(f, g, q):
    n = len(f)
    h = np.zeros(n, dtype=np.int64)
    for i in range(n):
        for j in range(n):
            kk = i + j
            if kk < n:
                h[kk] += f[i] * g[j]
            else:
                h[kk - n] -= f[i] * g[j]
    return h % q

rng = np.random.default_rng(seed=0)
A = rng.integers(low=0, high=q, size=(m, k, n), dtype=np.int64)
s = rng.integers(low=0, high=q, size=(k, n), dtype=np.int64)
raw_e = rng.integers(low=-B, high=B + 1, size=(m, n), dtype=np.int64)
e = raw_e % q

b = np.zeros((m, n), dtype=np.int64)
for i in range(m):
    row = np.zeros(n, dtype=np.int64)
    for j in range(k):
        row = (row + ring_mul_naive(A[i, j], s[j], q)) % q
    b[i] = (row + e[i]) % q

print("A shape =", A.shape)
# ==> A shape = (4, 2, 4)
print("s shape =", s.shape)
# ==> s shape = (2, 4)
print("b shape =", b.shape)
# ==> b shape = (4, 4)
print("b[0] =", b[0].tolist())
# ==> b[0] = [1, 15, 16, 9]

Each row of the matrix-vector product sums two ring multiplications and one error vector. At $k = 1$, the inner loop runs once and Module-LWE reduces to Ring-LWE with $m$ independent pairs sharing the same secret. At $k = 2$, each row is the sum of two ring products. At ML-KEM-768’s $k = 3$, the inner loop runs three times. At ML-KEM-1024’s $k = 4$, it runs four times. The number of inner ring multiplications is $m k$. At the toy parameters above that is $4 \cdot 2 = 8$ ring multiplications to assemble $\mathbf{b}$.

At ML-KEM-512, the public matrix $\mathbf{A}$ has shape $k \times k$ with $k = 2$, which is $k \cdot k \cdot n = 2 \cdot 2 \cdot 256 = 1024$ ring coefficients after expansion. The encapsulation key does not transmit those coefficients directly: it stores the NTT-domain target $\hat{\mathbf{t}}$ together with a $32$-byte seed $\rho$. The encapsulating party extracts $\rho$ from the encapsulation key and regenerates $\hat{\mathbf{A}}$ using ML-KEM’s XOF / SampleNTT procedure (National Institute of Standards and Technology, 2024). The secret is a vector of $k = 2$ ring elements, $2 \cdot 256 = 512$ integers. The Module-LWE form trades a slightly larger expanded matrix for a secret that is $k$ ring elements rather than one. That trade gives the designer an extra knob for tuning security against speed by varying $k$ (National Institute of Standards and Technology, 2024).

Worst-case reductions and structural attacks

A note on the cyclotomic framing. The Ring-LWE reduction uses a slightly different algebraic framing than the $R_q$ used in the previous sections. Let $\zeta_{2n}$ denote a primitive $2n$-th root of unity in $\mathbb{C}$. For $n$ a power of two, the minimal polynomial of $\zeta_{2n}$ over $\mathbb{Q}$ is the cyclotomic polynomial $\Phi_{2n}(x) = x^n + 1$. The cyclotomic field $\mathbb{Q}(\zeta_{2n})$ therefore has ring of integers $\mathbb{Z}[\zeta_{2n}]$ (Theorems 2.5 and 2.6 in Washington, 1997), and this ring is isomorphic as a $\mathbb{Z}$-algebra to the polynomial ring $\mathbb{Z}[x]/(x^n + 1)$ we have been computing in. Under the isomorphism, a polynomial $f \in \mathbb{Z}[x]/(x^n+1)$ corresponds to the algebraic integer $f(\zeta_{2n}) \in \mathbb{Z}[\zeta_{2n}]$.

An ideal lattice in $\mathbb{Z}[\zeta_{2n}]$ is a nonzero ideal $I \subseteq \mathbb{Z}[\zeta_{2n}]$ viewed as a rank-$n$ sublattice of $\mathbb{Z}[\zeta_{2n}]$ and, equivalently, as a rank-$n$ sublattice of $\mathbb{Z}^n$ via the coefficient representation (Lyubashevsky et al., 2010). For the power-of-two cyclotomic rings used in this chapter, the coefficient representation is well behaved and supports the toy arithmetic examples above.

Write $R = \mathbb{Z}[\zeta_{2n}]$ for this ring of integers. A module lattice of rank $k$ in $R^k$ is a finitely generated $R$-submodule of $R^k$ of full rank, one that contains $k$ $R$-linearly independent vectors (Section 2.1 in Langlois & Stehlé, 2015), viewed as a rank-$kn$ sublattice of $\mathbb{Z}^{kn}$ via the coefficient representation. At $k = 1$, module lattices specialize to ideal lattices.

What the reductions give. Both hardness results are quantum reductions from worst-case problems on these lattices to average-case problems over the same ring, for Gaussian errors. The Lyubashevsky-Peikert-Regev (LPR) 2010 theorem reduces approximate SVP on ideal lattices in $R$ to search Ring-LWE (Lyubashevsky et al., 2010, sec. 1.1). The Langlois-Stehlé 2015 theorem is the corresponding statement for module lattices of rank $k$ and Module-LWE at rank $k$, and at $k = 1$ it is the Ring-LWE theorem (Langlois & Stehlé, 2015, sec. 4.1). So an efficient algorithm for random instances of Ring-LWE or Module-LWE would give an efficient quantum algorithm for those approximate lattice problems on every ideal or module lattice, not only on random ones. Both theorems carry hypotheses on the modulus, on the width of the errors, and on the coordinates in which the errors are measured, and the note below states them.

What the theorems assume

Both reductions are naturally stated in the canonical embedding of $\mathbb{Q}(\zeta_{2n})$, not the coefficient representation this chapter computes in. Their exact Gaussian widths and dual ideals are stated in that embedding (Lyubashevsky et al., 2010). In Ring-LWE and Module-LWE, duality is usually formulated before reduction modulo $q$, in the number field and its ring of integers (Langlois & Stehlé, 2015, sec. 4.1; Lyubashevsky et al., 2010, sec. 2.3). The dual of the ring of integers is the dual ideal $R^\vee$, a fractional ideal also called the codifferent (Lyubashevsky et al., 2010, sec. 2.2). Under the canonical embedding, the dual of any fractional ideal embeds as the complex conjugate of the ideal’s dual lattice, as Chapter 7 defines it (Lyubashevsky et al., 2010, sec. 2.2). The original Ring-LWE reduction is stated for continuous Gaussian errors in the canonical embedding, added modulo the dual ideal $R^\vee$ (Lyubashevsky et al., 2010, sec. 2.3), and passing from there to a discrete coefficient-wise error is a separate translation.

For Ring-LWE, fix the cyclotomic ring $R = \mathbb{Z}[\zeta_{2n}]$ with $n$ a power of two. Fix $\alpha \in (0, 1)$ and a modulus $q \geq 2$ with $\alpha q \geq \omega(\sqrt{\log n})$, and ask for a solver that works for every error distribution in the family $\Psi_{\leq \alpha}$, the elliptical Gaussians in the canonical embedding whose width along each axis is at most $\alpha$. The Lyubashevsky-Peikert-Regev theorem then gives a polynomial-time quantum reduction from approximate shortest-vector problems on worst-case ideal lattices in $R$ to average-case search Ring-LWE over $R / qR$ with that error family. Its approximation factor grows with $1/\alpha$, and is polynomial in $n$ when $1/\alpha$ is (Lyubashevsky et al., 2010, sec. 3.1). A single fixed spherical Gaussian is not what the theorem is stated for. The paper notes that hardness for one costs a slightly super-polynomial approximation factor, modulus, and reduction runtime (Lyubashevsky et al., 2010, sec. 1.1). The proof uses the canonical embedding, the Chinese remainder theorem and the dual-basis theory of ideal lattices, tools that work in any number field, together with Regev’s iterative quantum reduction from the flat LWE paper (Lyubashevsky et al., 2010, sec. 1.1 and 3.1; Regev, 2009). Cyclotomic structure enters at the search-to-decision step below (Lyubashevsky et al., 2010, sec. 1.4).

For Module-LWE, fix the same ring $R$, a module rank $k \geq 1$, an $\alpha \in (0, 1)$, and a modulus $q \geq 2$ of known factorization with $\alpha q > 2\sqrt{k} \cdot \omega(\sqrt{\log n})$. In informal form, Langlois and Stehlé’s Theorem 4.7 gives a quantum polynomial-time reduction from approximate module-lattice problems, in particular Mod-SIVP, to average-case search Module-LWE over $R_q^k$ with the same error family $\Psi_{\leq \alpha}$ as above, at approximation factor $k \sqrt{8 n} \cdot \omega(\sqrt{\log n}) / \alpha$, which is polynomial in $kn$ when $1/\alpha$ is. The decision form follows by a direct search-to-decision step when $q$ is a prime bounded by a polynomial in $kn$ with $q \equiv 1 \pmod{2n}$, and for a modulus of any other shape through their Theorem 4.8, a modulus-switching step that enlarges the noise by a stated factor (Langlois & Stehlé, 2015, sec. 4.1).

The search-to-decision side of the LPR result is where the arithmetic conditions on $q$ arrive. That reduction is stated for a prime $q$, bounded by a polynomial in $n$, that splits completely in $\mathbb{Z}[\zeta_{2n}]$, which happens precisely when $q \equiv 1 \pmod{2n}$ (Lyubashevsky et al., 2010). None of the three is required by the worst-case reduction to search Ring-LWE above.

The splitting condition is the same condition as $2n \mid q - 1$, the condition that makes the negacyclic NTT available, from the “The number theoretic transform” section above. The coincidence is not accidental: splitting completely in the ring of integers is the algebraic content of the factorization $x^n + 1 = \prod_{i=0}^{n-1}(x - \psi^{2i+1})$ over $\mathbb{Z}_q$. The full-splitting condition is therefore both the condition for the simple full negacyclic NTT and one of the standard algebraic conditions in the LPR search-to-decision reduction for cyclotomic Ring-LWE. The problem variant and noise distribution still matter, so this is not the whole theorem.

ML-KEM is a useful counterpoint: $q = 3329$ admits primitive $256$-th roots but not primitive $512$-th roots, so $x^{256} + 1$ factors into $128$ quadratic pieces rather than $256$ linear ones, and Chapter 11’s partial NTT mirrors that incomplete splitting (National Institute of Standards and Technology, 2024).

Module-LWE sits between flat LWE and Ring-LWE in the amount of algebraic structure exposed. As $k$ grows, the structure is less concentrated in a single ideal-lattice component and the underlying module-lattice problem looks more like a general lattice problem (Langlois & Stehlé, 2015).

Practical schemes pick Module-LWE for flexibility. The ring $R_q = \mathbb{Z}_{3329}[x]/(x^{256}+1)$ supports three ML-KEM security levels by varying the module rank $k$ from $2$ to $4$, rather than three different rings at three different values of $n$ (National Institute of Standards and Technology, 2024).

Structural attacks. Ideal and module lattices are a narrower class of lattices than the general-lattice family that the flat LWE reduction covers. The narrower class leaves room for attacks that exploit the algebraic structure of the ring. Two structural attack families are worth flagging here, and each bites only in its own parameter regime.

The first targets Ring-LWE over specially chosen non-cyclotomic number fields whose error is too narrow for the field. Elias, Lauter, Ozman, and Stange built such instances from defining polynomials of the form $x^n + ax + b$ and solved their decision problem from $20$ samples, with success rates of $10$ to $80$ percent (Castryck et al., 2016, p. 149). Castryck, Iliashenko, and Vercauteren recovered the secret itself, from at most $7$ samples, in every run of every parameter set they report (Castryck et al., 2016, sec. 4.2). The error has the shape the Ring-LWE definition uses, a Gaussian in the canonical embedding, here spherical. Pulled back to polynomial coefficients through these particular fields, it becomes a very uneven ellipsoid whose narrowest coordinates round to zero, which turns the matching coordinates of each sample into exact linear equations in the secret (Castryck et al., 2016, sec. 4). The same observations apply to dual Ring-LWE over those fields. None of it contradicts LPR’s hardness theorem, because the error widths the attack needs are far below the ones that theorem requires (Castryck et al., 2016, sec. 5).

The second family targets cyclotomic rings with small proper subfields. Sub-field attacks exploit the factorization of the cyclotomic minimal polynomial over those subfields to reduce a high-dimensional ring problem to a lower-dimensional one on the subfield, where lattice reduction is cheaper. Albrecht, Bai, and Ducas 2016 give the canonical sub-field attack on overstretched NTRU and related ring-based instances (Albrecht et al., 2016). These attacks become efficient in the overstretched regime, where the modulus $q$ grows super-polynomially in $n$ and the norm map down to a proper subfield (including, for power-of-two cyclotomics, the maximal real subfield) produces a strictly cheaper lattice problem (Albrecht et al., 2016). Power-of-two cyclotomics are not immune on principle: their subfield tower is rich enough to support the norm map.

ML-KEM is not an NTRU instance, overstretched or otherwise. The sub-field attack norms an NTRU public key, a ratio of two short ring elements, down to a subfield (Albrecht et al., 2016). ML-KEM publishes a Module-LWE sample instead, and the Kyber team notes that the geometry of the NTRU lattice leads to attacks that do not exist against Ring-LWE or Module-LWE schemes (Avanzi et al., 2021, sec. 6.4.4). The team’s own analysis treats the Module-LWE instance as plain LWE, because the best attacks known in 2021 made no use of the structure in the lattice, and prices the primal and dual attacks on it (Avanzi et al., 2021, sec. 5.1). Hybrid attacks published in 2026 do use the ring, and Chapter 13 gives their gain at ML-KEM’s parameters, around one bit in their authors’ summary (Hou et al., 2026).

The lesson is that structural attacks remain highly parameter- and assumption-specific. Chapter 13 walks the best-known primal and dual attacks on ideal and module lattices at cryptographic parameters. It states the cost model and places the three ML-KEM parameter sets of FIPS 203 §8 (National Institute of Standards and Technology, 2024) on the resulting curve.

Tradeoffs inside Part II

Flat LWE (Chapter 8) is the source of lattice hardness with a quantum reduction from worst-case general-lattice problems (Regev, 2009). Ring-LWE compresses the public data by a factor of $n$ per algebraic relation and adds a fast-multiplication algorithm, at the cost of restricting to structured lattices (Lyubashevsky et al., 2010). Module-LWE interpolates between the two by varying the module rank $k$ (Langlois & Stehlé, 2015). Chapter 10 builds Regev-style public-key encryption over flat LWE, then shows the Ring-LWE descendant that replaces the flat sample $(A, b)$ with a ring sample $(a, b)$. Chapter 11 replaces the $\mathbb{Z}_q$ secret with a Module-LWE secret, adds the Fujisaki-Okamoto transform from Chapter 5, and lands on ML-KEM (National Institute of Standards and Technology, 2024). Chapter 13 walks the primal and dual attack families on ideal and module lattices. It places the three parameter sets of FIPS 203 §8, ML-KEM-512, ML-KEM-768, and ML-KEM-1024 (National Institute of Standards and Technology, 2024), on the best-known cost curve.

The hash-based signatures of Chapter 14 and Chapter 15 rest on preimage and collision resistance. Those are assumptions about concrete hash functions, not worst-case lattice problems. The code-based KEMs of Chapter 20 (Classic McEliece) and Chapter 21 (HQC) rest on syndrome decoding. The bounded-weight syndrome decoding decision problem is NP-complete (Berlekamp et al., 1978). That is a worst-case theorem. The concrete instances those schemes rest on need an average-case hardness assumption that no reduction from the worst case supplies, which Chapter 3 states as a working conjecture. The isogeny-based signature of Chapter 23 (SQIsign) rests on the endomorphism ring problem on supersingular elliptic curves. Its cryptanalytic surface is still being explored. The lattice family has a worst-case-to-average-case reduction from a well-studied geometric problem, the reductions stated above (Langlois & Stehlé, 2015; Lyubashevsky et al., 2010). Of the Part II through Part IV families surveyed here, it is the only one that does.

Exercises

Exercise 1. Negacyclic wraparound at $n = 8$. Using ring_mul_naive from the package or the inline definition in the first code block, multiply $f = x^5$ by $g = x^4$ in $R_{17} = \mathbb{Z}_{17}[x]/(x^8 + 1)$. By hand, the product in $\mathbb{Z}[x]$ is $x^9$. Reduce using $x^8 \equiv -1$ to get $-x$, then reduce modulo $17$ to get $16 x$. Run the function and verify that it prints $[0, 16, 0, 0, 0, 0, 0, 0]$. Now replace $g$ with $x^3$. The product in $\mathbb{Z}[x]$ is $x^8$, which reduces to $-1 = 16$. Verify the function prints $[16, 0, 0, 0, 0, 0, 0, 0]$.

Exercise 2. Forward NTT of $f = x$. At $(n, q, \psi) = (4, 17, 2)$, compute the forward NTT of $f = x$ by hand. The coefficient vector is $[0, 1, 0, 0]$. The result is $\hat{f}_k = \psi^{2k+1}$ for $k = 0, 1, 2, 3$. That is $(\psi, \psi^3, \psi^5, \psi^7) = (2, 8, 32, 128) \pmod{17}$, which reduces to $(2, 8, 15, 9)$. Run ntt_forward([0, 1, 0, 0]) from the package and verify it returns the same four values.

Exercise 3. Module-LWE at rank $k = 3$. Draw a Module-LWE instance at $(n, q, k, m, B) = (4, 17, 3, 4, 1)$ using sample_module_lwe from the package. Verify the defining identity by recomputing $\mathbf{b}[i] = \sum_{j=0}^{2} \mathbf{A}[i, j] \cdot \mathbf{s}[j] + \mathbf{e}[i]$ with ring_mul_naive on every term. Compare term by term against the returned $\mathbf{b}$. The test file tests/ch09/test_module_collapses_to_ring.py does this check for $k = 1, 2, 3$. The exercise is to write the verification yourself.

Exercise 4. Primes admitting the NTT at $n = 8$. The negacyclic NTT at $n = 8$ requires a prime $q$ with $16 \mid q - 1$. Write a short Python loop that finds every prime $q < 200$ satisfying this condition. Pick any such $q$ and use primitive_2n_root(8, q) from the package to find a primitive $16$-th root of unity $\psi$. Verify by hand that $\psi$ has order $16$: $\psi^{16} \equiv 1 \pmod q$ and $\psi^8 \not\equiv 1 \pmod q$. Run ntt_forward and ntt_inverse on a random polynomial and verify the round-trip.

Exercise 5. Why not another root? The block that attacks the cyclic ring keeps a guess for $s(1)$ when every residual lies within $nB$ of $0$, the largest value $|e(1)|$ can take. Figure 9.1 shows that $x^4 + 1$ has the root $2$ in $\mathbb{Z}_{17}$. Evaluation at $x = 2$ therefore respects addition and multiplication in $R_{17} = \mathbb{Z}_{17}[x]/(x^4 + 1)$, and every Ring-LWE sample over $R_{17}$ satisfies $b(2) = a(2)\,s(2) + e(2)$. At the toy parameters $(n, q, B) = (4, 17, 1)$, predict the largest value $|e(2)|$ can take. Then predict what the test keeps on Ring-LWE samples and on uniform ones if it evaluates at $2$ with its window widened to that value. Finally, explain what made $x = 1$ useful to the attacker.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 9. A separate track, for rebuilding rather than reading: the package exercises/ch09-ring-lwe has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch09 to grade your version against the suite that proves the reference one.

References

Albrecht, M. R., Bai, S., & Ducas, L. (2016). A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and graded encoding schemes. Advances in Cryptology – CRYPTO 2016, 9814, 153–178. https://doi.org/10.1007/978-3-662-53018-4_6

Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., & Stehlé, D. (2021). CRYSTALS-Kyber Algorithm Specifications and Supporting Documentation (Version 3.02). NIST Post-Quantum Cryptography Project, Round 3 submission package. https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf

Berlekamp, E. R., McEliece, R. J., & van Tilborg, H. C. A. (1978). On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24(3), 384–386. https://doi.org/10.1109/TIT.1978.1055873

Castryck, W., Iliashenko, I., & Vercauteren, F. (2016). Provably weak instances of Ring-LWE revisited. In M. Fischlin & J.-S. Coron (Eds.), Advances in Cryptology – EUROCRYPT 2016 (Vol. 9665, pp. 147–167). Springer. https://doi.org/10.1007/978-3-662-49890-3_6

Hou, J., Jiang, H., & Ogilvie, T. (2026). Careful with the Ring! Concrete Hardness Gaps Between LWE and MLWE. Advances in Cryptology – CRYPTO 2026. https://doi.org/10.1007/978-3-032-35377-1_15

Lang, S. (2002). Algebra (Revised 3rd, Vol. 211). Springer. https://link.springer.com/book/10.1007/978-1-4613-0041-0

Langlois, A., & Stehlé, D. (2015). Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75(3), 565–599. https://doi.org/10.1007/s10623-014-9938-4

Longa, P., & Naehrig, M. (2016). Speeding up the number theoretic transform for faster ideal lattice-based cryptography. In S. Foresti & G. Persiano (Eds.), Cryptology and Network Security – CANS 2016 (Vol. 10052, pp. 124–139). Springer. https://doi.org/10.1007/978-3-319-48965-0_8

Lyubashevsky, V., Peikert, C., & Regev, O. (2010). On ideal lattices and learning with errors over rings. In H. Gilbert (Ed.), Advances in Cryptology – EUROCRYPT 2010 (Vol. 6110, pp. 1–23). Springer. https://doi.org/10.1007/978-3-642-13190-5_1

National Institute of Standards and Technology. (2024). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.203

Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6), 34:1-34:40. https://doi.org/10.1145/1568318.1568324

Seiler, G. (2018). Faster AVX2 optimized NTT multiplication for Ring-LWE lattice cryptography. IACR Cryptology ePrint Archive. https://eprint.iacr.org/2018/039

Washington, L. C. (1997). Introduction to Cyclotomic Fields (2nd ed., Vol. 83). Springer. https://doi.org/10.1007/978-1-4612-1934-7