Module-LWE

Ring-LWE fixes everything through one number. The ring degree $n$ determines the key size, the security level, and the shape of the multiplication all at once.

That coupling is a practical problem. Raising security means raising $n$, which changes the ring, which changes the multiplication algorithm, which changes the hardware. A chip built for one security level would not serve another.

Module-LWE breaks the coupling.

01.The definition

Keep the ring $R_q$ fixed, and introduce a second parameter: the module rank $k$, a small integer.

A Module-LWE sample is a pair

$$(\mathbf{a},\; b) \;\in\; R_q^k \times R_q,$$

where $\mathbf{a}$ is a vector of $k$ uniform ring elements, the secret $\mathbf{s}$ is a vector of $k$ short ring elements, the error $e$ is a short ring element, and

$$b \;=\; \langle \mathbf{a}, \mathbf{s} \rangle + e \;=\; \sum_{i=1}^{k} a_i \cdot s_i \;+\; e .$$

So the secret is now $k$ polynomials rather than one, and producing a sample takes $k$ ring multiplications rather than one.

The two extremes are worth naming, because they show that Module-LWE is not a third thing but an interpolation between the two you already know.

Set $k = 1$ and the sum has one term, so a Module-LWE sample is exactly a Ring-LWE sample.

Set $n = 1$, so that $R_q$ collapses to $\mathbb{Z}_q$ and each polynomial is a single number, and a Module-LWE sample is exactly a plain LWE sample of dimension $k$.

Everything in between is available by choosing $n$ and $k$ independently.

02.What the extra knob buys

The lattice an attacker faces has dimension $k \cdot n$. That product is what determines security.

Because it is a product, security can be raised by increasing either factor. Module-LWE raises $k$ and leaves $n$ alone.

The consequence is the one that mattered to the standards committee. Every ML-KEM parameter set uses $n = 256$ and $q = 3329$. Every ML-DSA parameter set uses $n = 256$ and $q = 8380417$. Only $k$ changes across security levels.

So one implementation of the length-$256$ transform serves every parameter set of a scheme. In software that means one optimised routine rather than three. In hardware it means one datapath, and a chip that can be configured for any security level without re-synthesis. For a book whose eventual subject is hardware acceleration, this is the single most consequential design decision in the standards.

03.The parameter sets

Two things to read out of the table.

The numbers in the ML-KEM names are the effective lattice dimensions, not key sizes. ML-KEM-768 works over a lattice of dimension $768 = 3 \times 256$, and it is the parameter set NIST recommends as the general-purpose default.

ML-DSA carries two ranks rather than one. Signature schemes need a rectangular matrix, $k$ rows by $\ell$ columns, because signing and verification are not symmetric operations the way encryption and decryption are. Chapter 6 explains where each dimension goes.

Why not just use Ring-LWE with a bigger $n$

Given that Ring-LWE is simpler, the obvious question is why the standards took on the extra parameter.

Three reasons, in increasing order of importance.

Powers of two are coarse. Ring degrees have to be powers of two for the transform to work, so the available security levels with pure Ring-LWE would be $n = 256$, then $512$, then $1024$. That is a factor of two between adjacent levels, with nothing in between. Module rank gives $512$, $768$, $1024$, which is finer and lets ML-KEM-768 exist at all.

Hardware reuse, as above. One transform length serves everything.

And structure hedging. Ring-LWE at dimension $1024$ needs a single ring of degree $1024$, which is a large algebraic object with correspondingly more structure for an attacker to exploit. Module-LWE at effective dimension $1024$ uses four independent polynomials of degree $256$ each. The algebraic structure is confined to each degree-$256$ piece, and the relationship between the pieces is unstructured, exactly as in plain LWE. If a future attack exploits ring structure, it has a quarter as much to work with.

Module-LWE is therefore the deliberate middle of the range: most of Ring-LWE's compression, some of plain LWE's lack of structure, and a security knob that leaves the arithmetic alone.

The rest of this chapter is about that arithmetic, and specifically about making $a_i \cdot s_i$ fast.