Implementation Axes, and the Chapter Summary

Committing the transform to hardware forces a set of choices that the mathematics leaves open. This note names them, because they are where the engineering work in this area actually happens, and none of them is proprietary.

01.What a designer decides

Radix. Every butterfly in The Butterfly and Bit Reversal combined two values, which is radix-2. A radix-4 butterfly combines four at once, halving the number of levels at the cost of more multipliers and more complicated data routing per stage. Radix-8 goes further. The trade is level count against area, and the best point depends on the memory feeding it more than on the arithmetic itself.

Memory banking. Both operands of a butterfly have to arrive in the same cycle. A single-port memory delivers one word per cycle, so the datapath stalls half the time. A dual-port memory removes the stall and costs substantially more area. Conflict-free access schedules exist that let a banked single-port arrangement behave like a dual-port one, at the cost of an address-generation network. This is usually the hardest part of the design, and it is a memory problem rather than an arithmetic one.

Reduction inside the butterfly. The multiplication produces a value roughly twice the coefficient width, and it has to come back down before the next level. That reduction sits in the critical path of every butterfly, so its latency multiplies by $\frac{n}{2}\log_2 n$ across a transform. Barrett, Montgomery and Plantard reduction are the three candidates, and choosing among them is the subject of Chapter 7.

Pipelining against unfolding. One pipelined butterfly unit processes a pair per cycle and completes a transform in roughly $\frac{n}{2}\log_2 n$ cycles with minimal area. A fully unfolded design instantiates a butterfly for every pair at every level and completes in $\log_2 n$ cycles with enormous area. The literature covers the whole spectrum between them, and the interesting designs sit in the middle.

A shared datapath. ML-KEM needs seven levels of length-128 butterflies. ML-DSA needs eight levels of length-256. A device supporting both standards would like one engine rather than two. Whether that is achievable without paying most of the area of two separate engines is a genuine open engineering question, and it is the one the research arc this book supports is aimed at.

02.Chapter summary

Ring-LWE replaces the vectors of plain LWE with elements of $R_q$. One ring sample carries as much information as $n$ plain samples, because multiplying by a fixed polynomial is the same as multiplying by its negacyclic circulant matrix, and that matrix is entirely determined by the polynomial's $n$ coefficients. Storing $n$ numbers stores $n^2$ of them, which is where the key compression comes from. The price is a stronger assumption, since the matrix is no longer fully random.

Module-LWE adds a rank $k$ and stacks $k$ ring elements, so security can be raised by changing $k$ while $n$ stays at $256$. That is why all six standardised parameter sets share one transform length, and why one hardware datapath can serve all of them.

Schoolbook multiplication in $R_q$ costs $n^2$ coefficient multiplications, about $65{,}000$ at $n = 256$, and a single scheme operation needs a dozen or more such products. The Number Theoretic Transform brings it down by about a factor of twenty.

It works because a polynomial is equally determined by its coefficients or by its values at enough points, and multiplication in the second representation is pointwise and therefore linear. Evaluating at $n$ arbitrary points would cost $n^2$ and save nothing, so the points are chosen as powers of a root of unity, which lets the recursion share work and brings the cost to $n \log n$.

The negacyclic version, which is what $X^n + 1$ requires, evaluates at the $n$ odd powers of a primitive $2n$th root of unity, and those are exactly the roots of $X^n + 1$. That imposes the condition $2n \mid q - 1$.

The atomic operation is the butterfly, $A' = A + tB$ and $B' = A - tB$, and there are $\frac{n}{2}\log_2 n$ of them. It runs in place and produces its output in bit-reversed order, which implementations deliberately leave unsorted because the permutation cancels against the inverse transform.

ML-DSA satisfies the divisibility condition comfortably and runs the complete transform with $\zeta = 1753$. ML-KEM does not, because $3329 - 1 = 2^8 \cdot 13$ has one factor of two too few, so it runs an incomplete seven-level transform with $\zeta = 17$ and pays about a factor of two. That was accepted deliberately, to keep coefficients at $12$ bits everywhere else.

The next chapter uses all of this to build ML-KEM, and the transform stops being a topic and becomes an assumed primitive that everything else calls.