Hardware Footprint, and the Chapter Summary

01.Building the permutation

The straightforward design stores the 1600-bit state in flip-flops and applies one round per cycle. The dominant logic is $\theta$'s XOR tree, which is wide but shallow, and $\chi$'s AND-XOR network. The two free steps, $\rho$ and $\pi$, contribute wiring only.

Four points on the trade-off curve.

One round per cycle. About 15 to 20 thousand LUTs on a small FPGA such as an Intel MAX 10 or Xilinx Artix-7, running at 100 to 150 MHz, taking 24 cycles per permutation. This is the balanced choice.

Two rounds per cycle. Cascade two round functions combinationally. The cycle count halves and the logic depth doubles, so the maximum frequency typically falls to 80 to 100 MHz. The net throughput gain is modest against a real area cost.

Bit-serial. Process one lane pair per cycle. Area falls below a tenth of the one-round design, and the cycle count multiplies by roughly 25. Only for severely constrained embedded targets.

Fully unrolled and pipelined. A register between every pair of rounds gives one finished block per cycle after 24 cycles of warm-up. Very high throughput, at a register and routing cost that overwhelms a small or mid-range FPGA.

For the target this book's research arc has in mind, open-source PDKs and FPGA boards under a few hundred dollars, one round per cycle is the sweet spot. A small FIFO between absorb and squeeze lets the transform engine and the Keccak engine overlap, so Keccak is rarely the sole bottleneck.

02.The shape of a complete accelerator

Pulling the whole book together, an accelerator for either standard has three blocks.

A transform engine, from Chapter 4: a butterfly datapath, a twiddle ROM, and the memory banking that keeps both operands available in one cycle.

A reduction unit in the butterfly's critical path, which is Montgomery or Plantard for ML-KEM and shifts-and-adds for ML-DSA.

A Keccak engine feeding both, supplying the matrix expansion, the noise sampling, and every hash.

Around them sits control logic, and for ML-DSA the rejection loop from Chapter 6, which must be able to discard an attempt and restart.

The two open questions the arc is aimed at both concern sharing. Can one transform datapath serve ML-KEM's incomplete length-128 transform and ML-DSA's complete length-256 one without paying for two? And given that the reduction tails cannot be shared, what does a design pay to support both?

The Keccak engine, at least, is unambiguously shared. Both standards use the identical permutation.

03.Chapter summary

Modular reduction cannot use division, which is twenty to forty cycles on a processor and large and slow in hardware, and which happens tens of thousands of times per handshake. It has to be built from multiplication, addition and shifts. The freedom to do so comes from $q$ being a compile-time constant, so anything depending only on $q$ is precomputed once.

Barrett multiplies by a precomputed scaled reciprocal $m = \lfloor 2^k / q \rfloor$, shifts, and multiplies back. The quotient estimate is within one of the truth, so one conditional subtraction finishes it. For ML-KEM's modulus at $k = 26$ the constant is $20158$, and the source manuscript's $20159$ is wrong in a way that still passes its own worked example while breaking the bound the correctness argument depends on.

Montgomery changes representation instead, holding every value as $xR \bmod q$ so that reduction becomes a shift by a power of two. It is worth its conversion cost only over a long chain of multiplications, which is exactly what a transform is, so implementations keep coefficients in Montgomery-NTT form nearly everywhere.

Plantard, from 2021, combines the two and lands the answer in a symmetric range with one fewer multiplier-touching step, giving ten to twenty percent frequency improvements on current FPGA fabric. It is under-represented in the published accelerator literature and is an open design point.

Special primes beat all three when available. ML-DSA's $q = 2^{23} - 2^{13} + 1$ gives $2^{23} \equiv 2^{13} - 1$, so reduction is a shift and two adds with no multiplication at all. ML-KEM's $3329$ has no such structure, which means a shared accelerator cannot share its reduction tail.

On the hashing side, a sponge is a permutation plus a rate-capacity split. Absorbing XORs input blocks into the rate and permutes. Squeezing reads the rate and permutes again. The capacity is never touched directly and sets the security level at about $2^{c/2}$. One construction therefore serves as hash, stream cipher, pseudorandom function and key derivation function, which is why both standards need only one hash engine. SHAKE128 is the fast one and SHAKE256 the strong one, and a single domain byte is the only difference between SHA3 and SHAKE.

Keccak-$f$[1600] is 24 rounds of five steps on a $5 \times 5$ grid of 64-bit lanes. $\theta$ diffuses through column parities, turning one flipped bit into eleven. $\rho$ and $\pi$ rotate and rearrange lanes and are free in hardware. $\chi$ contributes the single AND gate that is the entire non-linearity of the design. $\iota$ adds a round constant so that no two rounds are alike. The whole permutation uses only XOR, AND, NOT and constant rotations, with no data-dependent behaviour anywhere, so it is constant-time by construction rather than by discipline.

That is the bottom of the stack. Seven chapters ago this book started with a symbol, $R_q = \mathbb{Z}_q[X]/(X^n+1)$, and no reason to care about it. It ends with the gates.