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 , with a power of two. A Ring-LWE sample is a pair of ring elements with . The secret is a polynomial drawn uniformly from , and the error has small coefficients from a short distribution (Lyubashevsky et al., 2010). A flat LWE instance at the same dimension stores an matrix of field elements. Ring-LWE stores one polynomial instead. The implicit negacyclic circulant that multiplication by realizes is never written down.
Module-LWE is the same idea at rank . The secret is a vector in , the public data is an matrix of ring elements, and the error is a vector in . At , Module-LWE coincides with Ring-LWE. At , the ring collapses to and Module-LWE coincides with flat LWE. ML-KEM uses Module-LWE at module rank over the single ring for its three security levels (National Institute of Standards and Technology, 2024). The number theoretic transform makes polynomial multiplication in run in time at the parameters practical schemes pick, under a simple arithmetic condition on .
The ring R_q and its negacyclic multiplication
Section titled “The ring R_q and its negacyclic multiplication”Fix a prime and an integer that is a power of two. The ring
consists of equivalence classes of polynomials in modulo the polynomial . A canonical representative is a polynomial of degree strictly less than . We write it as a length- coefficient vector with . Addition is coefficient-wise modulo : . Multiplication starts in and then uses two reductions. The polynomial product has degree at most . Every coefficient at position with is moved to position with a sign flip. The sign flip comes from in , which rearranges to . After the fold, every coefficient is reduced modulo . The whole operation takes integer multiplications (Lang, 2002).
The sign flip is the difference between and the cyclic ring . The cyclic modulus always carries the visible root , because . The negacyclic modulus avoids that particular factor. It may still factor over , and when it splits completely into 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 , , , and . The product in is
The single term above degree is . Applying subtracts from the constant term and leaves the higher terms alone. The folded polynomial is . Reducing each coefficient modulo gives the final answer in :
The constant term is . The other three are , , and . 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 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
Section titled “Ring-LWE and Module-LWE”A Ring-LWE instance is specified by a parameter tuple . Here is the ring degree, is the prime modulus, is the number of samples, and is a short error distribution over ring elements (Lyubashevsky et al., 2010). In the toy code below, “short” means coefficient-wise small: draws each coefficient uniformly from for a nonnegative integer noise bound . The original Ring-LWE reduction is stated for continuous Gaussian errors in the canonical embedding, added modulo the dual ideal , and passing from there to a discrete coefficient-wise error is a separate translation (Lyubashevsky et al., 2010, sec. 2.3). ML-KEM specifies its small ring elements through a centered binomial distribution , parameterized by an integer (National Institute of Standards and Technology, 2024). These are all short-noise choices, but they should not be treated as automatically interchangeable inside the worst-case reduction: the proof assumptions and the concrete security estimates have to be tracked separately.
Search Ring-LWE. Fix and draw uniform in , uniform in , and from . Set in . The search problem gives the solver independent samples that all share the same secret . The task is to recover (Lyubashevsky et al., 2010). The solver sees the pairs and the parameters. The secret and the errors are hidden. At , the advantage is the probability of recovering from one sample. At larger , the solver gets independent algebraic relations on the same secret.
Decisional Ring-LWE. The decisional problem presents samples drawn from one of two distributions with equal probability. On the Ring-LWE side, each for a fixed secret and independent from . On the uniform side, each is drawn independently and uniformly from . The solver must decide which (Lyubashevsky et al., 2010). Decisional Ring-LWE is the distinguishing game at the heart of every IND-CPA-secure scheme built on the ring. Search and decisional Ring-LWE are equivalent up to polynomial factors for a prime bounded by a polynomial in with , 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 , 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 and consider one sample with . Write the coefficients of as and the coefficients of as a column vector . The coefficients of the ring product are the entries of a matrix-vector product , where is a negacyclic circulant determined by .
The matrix is built column by column. The first column is , which is the coefficient vector of . 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 : when a coefficient is shifted past the top, it comes back negated. The last column is .
The matrix has entries, but only of them are free. The other are determined by the first column. One element therefore replaces the full matrix in the flat-LWE presentation.
The compression factor grows with . Flat LWE at secret dimension and sample count stores an matrix, which is field elements of public data. Ring-LWE at the same and stores ring elements, which is also field elements. The savings appear when compared against the algebraic yield of each sample. Each ring element carries linear equations on the coefficients of . One Ring-LWE sample is therefore comparable to rows of a flat LWE matrix. The public data per linear equation drops from field elements in flat LWE to one field element in Ring-LWE. That factor-of- compression is the practical appeal of the ring form.
The price of the compression is structure: the relations from one Ring-LWE sample are not independent flat-LWE rows, but correlated through the negacyclic-circulant form of . Ring-LWE is flat LWE restricted to a special algebraic family of matrices, not flat LWE with fewer bytes. The compression is what lets ML-KEM keep encapsulation keys small at every security level: bytes for ML-KEM-512, bytes for ML-KEM-768, and bytes for ML-KEM-1024 (National Institute of Standards and Technology, 2024).
Module-LWE generalizes Ring-LWE from one ring element to a rank- vector. A Module-LWE instance is specified by a parameter tuple , where is the module rank. Draw uniform, uniform, and with each entry from . Set in . The search problem is to recover from . The decisional version distinguishes from with uniform in (Langlois & Stehlé, 2015).
Two collapse identities place Module-LWE between the two endpoints. At , the matrix degenerates to a column of ring elements. Each row is then one Ring-LWE sample sharing the same secret . At , the ring degenerates to via the explicit isomorphism . A residue class modulo is determined by its value at , which is a single field element. Module-LWE at is flat LWE at secret dimension . Between the two endpoints, Module-LWE with and 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 | Secret | Worst-case hardness source |
|---|---|---|---|
| Flat LWE | field elements | GapSVP and SIVP on general lattices (Regev, 2009) | |
| Ring-LWE | field elements | one polynomial in | ideal-lattice problems in (Lyubashevsky et al., 2010) |
| Module-LWE | field elements | module-lattice problems such as Mod-SIVP at rank (Langlois & Stehlé, 2015) |
Those figures count the coefficients of alone, not the full public sample . Adding gives field elements for flat LWE, for Ring-LWE at samples, and 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 linear relations, one per coefficient of the ring product. At equal storage that is times as many constraints. At equal total public storage the ratio is instead, because Ring-LWE spends half its bytes on where flat LWE spends one part in . Module-LWE interpolates: each row of pairs with one entry of to give scalar relations, and those relations couple all ring-valued secret components rather than constraining each of them separately.
The number theoretic transform
Section titled “The number theoretic transform”The schoolbook multiplication in costs integer multiplications per ring product. At toy parameters this is invisible. At ML-KEM’s , 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 convolution with three transforms and an pointwise multiplication. The replacement holds when a single arithmetic condition on is satisfied.
The condition is that contains a primitive -th root of unity . A primitive -th root is a field element of multiplicative order exactly . That is: , and for every proper divisor of . The multiplicative group is cyclic of order . An element of order exists if and only if divides . At this holds because . At ML-KEM’s the condition fails: , and does not divide . ML-KEM uses a partial NTT that Chapter 11 develops. It works around the failure by using a primitive -th root and stopping the factorization one level early.
Negacyclic factorization. When , the polynomial splits into distinct linear factors over :
The factor carries the even powers: . The factor carries the odd powers:
This is the defining identity for the ring . The modulus is a product of distinct linear factors over . The Chinese remainder theorem then gives a ring isomorphism
Each factor on the left is a copy of . The identification is: reducing modulo a linear polynomial evaluates at (Lyubashevsky et al., 2010). The explicit map from left to right is evaluation at the odd powers of . A polynomial goes to the tuple . 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 , , and a primitive -th root . The NTT of a coefficient vector is the length- vector defined by
for . The -th entry is exactly . Because the isomorphism is a ring homomorphism, the product in satisfies pointwise over .
The inverse transform. The CRT isomorphism has an explicit inverse from an orthogonality relation. Fix and in and compute
Pull the factor out of the sum. What remains is , where is a primitive -th root of unity. The geometric-series identity for roots of unity gives when and otherwise. For this collapses to . The original sum is then when and otherwise. Rearranging, the inverse NTT is
for . The inverse uses the same sum structure as the forward transform. It uses in place of and a final multiplication by . Both and exist in because is prime.
At , a primitive -th root of unity is . The verification is a chain of exponentiations. We have , , , and . So has order exactly . At , a primitive -th root is . The check is , from which and no smaller divisor of gives . The package helper primitive_2n_root(n, q) searches until it finds an element of order . It caches the result by .
Figure 9.1 shows the negacyclic factorization at , . The polynomial factors over into four distinct linear factors , where is a primitive -th root of unity. The NTT evaluates a polynomial at these four points. It delivers the tuple as the image of in . Pointwise multiplication in corresponds to multiplication in . The inverse NTT recovers the coefficient vector from the evaluations.
A tiny NTT, end to end. The inline code block below implements the negacyclic NTT from the direct definition at . It transforms and , multiplies pointwise, inverse-transforms, and prints the result. The output matches the schoolbook product computed by hand earlier.
import numpy as np
n, q, psi = 4, 17, 2psi_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) % qh = 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]The direct-definition form runs in 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 -point transform splits into two -point transforms plus a linear combination. The input is pre-multiplied by the appropriate powers of before the DFT layer. The pre-twist makes the final evaluation points the odd powers of rather than the even powers. Production implementations in Kyber (the pre-standard NIST PQC submission) and ML-KEM use this layered form with a cache-friendly byte layout and a constant-time Montgomery reduction schedule (Longa & Naehrig, 2016; Seiler, 2018). Chapter 11 walks the iterative NTT 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 and 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
Section titled “Sampling Ring-LWE and Module-LWE in Python”Fix the toy parameters . The ring degree is , the modulus is the prime , and the noise bound is . Every error coefficient therefore lies in before reduction modulo . The code block below draws one Ring-LWE sample. It verifies the defining identity in using the schoolbook multiplication from the first section.
import numpy as np
n, q, B = 4, 17, 1rng = 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 % qb = (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 = 7folded = 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) % qprint("independent expected b =", expected_b.tolist())# ==> independent expected b = [10, 13, 3, 14]print("b == expected :", (b == expected_b).all())# ==> b == expected : TrueThe secret has four coefficients drawn uniformly from . The ring element has the same shape. The error has four coefficients drawn from , with one zero entry for this seed. The final print confirms that the returned matches the formula used to build it. The function sample_ring_lwe in the ch09-ring-lwe package under solutions/ returns the full tuple . Tests can then verify the identity directly.
Module-LWE at rank . ML-KEM-512 uses Module-LWE at rank over its ring. The toy version at has the same shape on a much smaller ring. The code block below samples a matrix of four rows and two columns of ring elements. It also samples a secret of two ring elements, an error vector of four ring elements, and the target .
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 , the inner loop runs once and Module-LWE reduces to Ring-LWE with independent pairs sharing the same secret. At , each row is the sum of two ring products. At ML-KEM-768’s , the inner loop runs three times. At ML-KEM-1024’s , it runs four times. The number of inner ring multiplications is . At the toy parameters above that is ring multiplications to assemble .
At ML-KEM-512, the public matrix has shape with , which is ring coefficients after expansion. The encapsulation key does not transmit those coefficients directly: it stores the NTT-domain target together with a -byte seed . The encapsulating party extracts from the encapsulation key and regenerates using ML-KEM’s XOF / SampleNTT procedure (National Institute of Standards and Technology, 2024). The secret is a vector of ring elements, integers. The Module-LWE form trades a slightly larger expanded matrix for a secret that is ring elements rather than one. That trade gives the designer an extra knob for tuning security against speed by varying (National Institute of Standards and Technology, 2024).
Worst-case reductions and structural attacks
Section titled “Worst-case reductions and structural attacks”A note on the cyclotomic framing. The Ring-LWE reduction uses a slightly different algebraic framing than the used in the previous sections. Let denote a primitive -th root of unity in . For a power of two, the minimal polynomial of over is the cyclotomic polynomial . The cyclotomic field therefore has ring of integers , and this ring is isomorphic as a -algebra to the polynomial ring we have been computing in (Washington, 1997). Under the isomorphism, a polynomial corresponds to the algebraic integer .
An ideal lattice in is a nonzero ideal viewed as a rank- sublattice of and, equivalently, as a rank- sublattice of 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.
Ring-LWE hardness from ideal lattices. The Lyubashevsky-Peikert-Regev 2010 theorem gives the hardness story for Ring-LWE. Fix the cyclotomic ring with a power of two. The theorem says the following. Fix and a modulus with , and ask for a solver that works for every error distribution in the family , the elliptical Gaussians in the canonical embedding whose width along each axis is at most . The theorem gives a polynomial-time quantum reduction from approximate shortest-vector problems on worst-case ideal lattices in to average-case search Ring-LWE over with that error family. Its approximation factor grows with , and is polynomial in when 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 reduction transfers worst-case hardness of approximate SVP on this narrower class of lattices to average-case hardness of Ring-LWE over the same ring (Lyubashevsky et al., 2010).
The exact statement tracks the canonical embedding, dual ideals, modulus conditions, and the width of the noise distribution. The proof uses cyclotomic-field structure, the dual-basis theory of ideal lattices, and Regev’s iterative quantum reduction from the flat LWE paper (Lyubashevsky et al., 2010; Regev, 2009).
The search-to-decision side of the LPR result is where the arithmetic conditions on arrive. That reduction is stated for a prime , bounded by a polynomial in , that splits completely in , which happens precisely when (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 , 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 over . 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: admits primitive -th roots but not primitive -th roots, so factors into quadratic pieces rather than linear ones, and Chapter 11’s partial NTT mirrors that incomplete splitting (National Institute of Standards and Technology, 2024).
Module-LWE hardness from module lattices. The Langlois-Stehlé 2015 theorem is the corresponding statement for Module-LWE. Fix the same ring , a module rank , an , and a modulus of known factorization with . In informal form, their 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 with the same error family as above, at approximation factor , which is polynomial in when is. The decision form follows by a direct search-to-decision step when is a prime bounded by a polynomial in with , 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). A module lattice of rank in is a finitely generated -submodule of of full rank, one that contains -linearly independent vectors, viewed as a rank- sublattice of via the coefficient representation. At , module lattices specialize to ideal lattices, and the module-lattice framework recovers the Ring-LWE endpoint.
Module-LWE sits between flat LWE and Ring-LWE in the amount of algebraic structure exposed. As 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 supports three ML-KEM security levels by varying the module rank from to , rather than three different rings at three different values of (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 specific non-dual or non-cyclotomic rings. Castryck, Iliashenko, and Vercauteren revisited earlier weak-instance results and showed that distinguishing attacks on these rings succeed at cost far below what flat LWE would face at the same dimension (Castryck et al., 2016). These weak instances exploit non-dual or distorted error embeddings rather than the canonical Gaussian embedding that LPR assumes (Castryck et al., 2016).
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 grows super-polynomially in 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 projection.
ML-KEM is not in the overstretched NTRU regime that these attacks target. Its modulus is fixed at with , so its security estimates are dominated by the usual primal, dual, and hybrid lattice attacks on Module-LWE rather than by sub-field projection (Albrecht et al., 2016). 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
Section titled “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 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 (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 with a ring sample . Chapter 11 replaces the 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
Section titled “Exercises”Exercise 1. Negacyclic wraparound at . Using ring_mul_naive from the package or the inline definition in the first code block, multiply by in . By hand, the product in is . Reduce using to get , then reduce modulo to get . Run the function and verify that it prints . Now replace with . The product in is , which reduces to . Verify the function prints .
Exercise 2. Forward NTT of . At , compute the forward NTT of by hand. The coefficient vector is . The result is for . That is , which reduces to . Run ntt_forward([0, 1, 0, 0]) from the package and verify it returns the same four values.
Exercise 3. Module-LWE at rank . Draw a Module-LWE instance at using sample_module_lwe from the package. Verify the defining identity by recomputing with ring_mul_naive on every term. Compare term by term against the returned . The test file tests/ch09/test_module_collapses_to_ring.py does this check for . The exercise is to write the verification yourself.
Exercise 4. Primes admitting the NTT at . The negacyclic NTT at requires a prime with . Write a short Python loop that finds every prime satisfying this condition. Pick any such and use primitive_2n_root(8, q) from the package to find a primitive -th root of unity . Verify by hand that has order : and . Run ntt_forward and ntt_inverse on a random polynomial and verify the round-trip.
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
Section titled “References”Last updated: