What the Ring Structure Costs: MOD-LWE Versus Plain LWE

The first lattice schemes that reached deployment used matrices of integers modulo $q$: the public key was a random $m \times n$ matrix, the secret was a vector, and the arithmetic was schoolbook matrix-vector multiplication. The keys were large, the products were expensive, and a single one of these facts is enough to make a protocol designer reach for something smaller. Replacing the matrix with multiplication in the ring $\mathbb{Z}_q[X]/(X^n+1)$ turns an $n^2$ operation into an $n \log n$ operation and collapses a full matrix into one polynomial, and the resulting schemes are what the standards actually specify. The structure is not free, and the cost is paid in the assumptions the security proof can make.

The three levels of structure and their sizes

Plain LWE, ring-LWE and module-LWE differ only in where the randomness lives. In plain LWE the public key is a dense matrix over $\mathbb{Z}_q$ of size $m \times n$ with $m$ proportional to $n$, so the key size is $O(n^2 \log q)$ bits. In ring-LWE the matrix is a single circulant-like structure generated by one polynomial, so the key is $O(n \log q)$ bits, a factor of $n$ smaller. Module-LWE sits between: the matrix is a $k \times k$ matrix over the ring, so the key is $O(k^2 n \log q)$ bits, and $k$ is a small constant chosen per parameter set.

ML-KEM’s parameter sets show the resulting sizes. The public key for ML-KEM-768 is 1184 bytes, of which 1152 bytes are the vector $t$ and 32 are the seed. A plain-LWE scheme at a comparable security level would need a matrix of at least a few hundred rows and columns, with each entry a 12-bit integer, which puts the public key in the hundreds of kilobytes. The comparison is the argument for the ring: the structure is what makes the key fit in a TLS ClientHello without dominating the message.

The arithmetic speedup is the same factor seen from the other side. Multiplying two ring elements costs $O(n \log n)$ field operations with the number-theoretic transform, against $O(n^2)$ for a dense matrix-vector product at the same dimension. The transform requires a primitive $2n$-th root of unity modulo $q$, and for $q = 3329$ and $n = 256$ such a root exists because $3329 - 1 = 2^8 \cdot 13$. That condition is why the modulus is chosen as a prime close to a power of two times a small integer rather than an arbitrary one: the factorisation of $q - 1$ has to contain a large power of two.

The algebraic advantage that the structure hands to an attacker

A ring element in $\mathbb{Z}_q[X]/(X^n+1)$ factors into irreducible factors over $\mathbb{Z}_q$, and the number-theoretic transform is precisely the Chinese remainder decomposition into those factors. For $q$ with the right order conditions, $X^n+1$ splits into $n/2$ quadratic factors, and each factor corresponds to an evaluation point which is a root of unity in an extension of $\mathbb{Z}_q$. An attacker who knows the factorisation can attack each factor independently: the ring-LWE instance decomposes into $n/2$ independent instances over the smaller modulus $q^2$, and if solving any one of them is easy, the whole instance falls.

This decomposition is the basis of the known attacks on structured instances. When $q$ is chosen so that $X^n + 1$ splits completely over $\mathbb{Z}_q$, the ring-LWE instance decomposes completely, and the attack reduces to instances over $\mathbb{Z}_q$ of a much smaller dimension that can be solved by exhaustive search or by small lattice reduction. The security then depends on the dimension of the factors, not on $n$. The standard parameter selection avoids this by choosing $q$ and $n$ so that the factors are as large as possible, which is why $q = 3329$ gives $X^{256}+1$ splitting into 128 quadratics rather than 256 linears: the factorisation does not go all the way down, and the attack surface is the 128 instances of a degree-2 problem rather than 256 separate ones.

The general lesson is that the ring’s algebraic structure creates a dual view of the problem. The attack does not need to break the lattice; it needs to break an instance that has been split into something smaller. Ring-LWE was proven hard for certain choices of $q$ and number field, in a reduction from ideal lattice problems, but that proof constrains the parameters in ways that the practical schemes do not satisfy. The schemes are analysed against the concrete attacks instead, and the “provably weak instances” literature is the record of what happens when the parameter choice ignores the factorisation.

Why the module form is the compromise

Module-LWE replaces the single ring element with a vector of $k$ elements, and the public matrix is $k \times k$ over the ring. The algebra of the ring is unchanged; what changes is the dimension of the free module over it. The effect on the attack is that the decomposition into $n/2$ quadratic factors now produces $n/2$ independent module instances of dimension $k$, rather than one instance of dimension $kn$. An attacker who can solve a dimension-$k$ module problem efficiently breaks the whole thing; an attacker who needs the full dimension is no better off than against plain LWE at the same total dimension.

This is the sense in which module-LWE interpolates. At $k = 1$ it is ring-LWE; at $k$ equal to the matrix dimension it is plain LWE. The practical choice of $k = 2, 3, 4$ for the three ML-KEM categories is a trade: larger $k$ gives a stronger security argument against algebraic attacks at the price of a larger key and slower multiplication, and the standards pick the smallest $k$ that the analysis supports at each category.

The trade-off is visible in the parameter tables. ML-KEM-512 uses $k = 2$ and claims category 1, ML-KEM-768 uses $k = 3$ and claims category 3, ML-KEM-1024 uses $k = 4$ and claims category 5. The key sizes grow as $k^2$: 800, 1184 and 1568 bytes for the public key, which is the $k^2$ scaling with the 12-bit coefficient encoding. The ciphertext sizes grow as $k$: 768, 1088 and 1568 bytes, because the $u$ component has $k$ polynomials and $v$ has one. A protocol that needs the highest category for a signature exchange pays the ciphertext cost per handshake, which is why the choice between categories is a bandwidth decision as much as a security one.

Rings that are not power-of-two cyclotomics

The choice $X^n + 1$ with $n$ a power of two is the easiest case: the polynomial is irreducible over the integers, the ring has no zero divisors, and the transform is straightforward. Other cyclotomic polynomials $X^n + 1$ with $n$ not a power of two are irreducible too, but the transform requires an $n$-th root of unity modulo $q$, and the factorisation patterns are more varied. Schemes that use them have to analyse the splitting for each parameter choice rather than relying on a uniform argument, and the literature on which choices are safe is correspondingly more delicate. The practical schemes avoid the issue by fixing $n$ at 256, which is the largest power of two below the point where the key sizes become impractical, and varying $k$ instead.

The constraint interacts with the modulus in a way that is easy to miss. For the transform to exist, $2n$ must divide $q - 1$. For $n = 256$ that means $512 \mid q - 1$, so $q \equiv 1 \pmod{512}$. A prime near 3329 with that property is exactly the choice made, and primes near 4096 or 2048 with the same property are the alternatives that appear in other schemes. The security analysis then evaluates those candidates against the reduction and chooses the one with the best trade-off between modulus size and factorisation pattern. The same reasoning appears in the noise budget for ML-KEM, where the modulus determines how much noise can be tolerated before decryption fails, and in basis reduction where the dimension and the modulus jointly set the attack cost.

Nothing in this validates the module form as a proof of security. The reduction from module-LWE to worst-case module lattice problems is known under parameter conditions, and the concrete security is estimated against the algorithms in the literature. The structure buys key size and speed at the cost of an attack surface that has to be checked for each parameter set, and the check is the ongoing cryptanalytic work that the standards cite rather than a theorem. That is the same epistemic position as the code-based schemes described in syndrome decoding hardness, with a different and better-understood structure, and the two together are what a post-quantum deployment rests on.