Chapter 7: Modular Reduction and the Keccak Sponge

01.What this chapter is for

Chapters 5 and 6 specified the two standards. This one goes underneath them, to the two operations that every part of both schemes actually spends its time in.

The first is reducing a product modulo $q$. Every butterfly in the transform multiplies two coefficients and gets something roughly twice as wide, which has to come back down before the next level. There are around a thousand butterflies per transform and a dozen transforms per operation, so this happens tens of thousands of times per handshake. It sits in the critical path of everything.

The second is the Keccak permutation. Chapter 5 noted that every random byte either scheme uses comes from Keccak in one parameterisation or another: expanding the matrix, sampling the noise, hashing the message, deriving the key. One primitive serves all of it.

Neither is cryptography in the sense the earlier chapters were. Both are the difference between a specification and something that runs.

02.Who this is written for

The same reader, with one shift in emphasis. This is the chapter closest to hardware, and it is where implementation cost stops being a footnote and becomes the subject. No new mathematics is introduced beyond ordinary integer arithmetic and the bitwise operations XOR, AND, NOT and rotate, all of which are defined where they appear.

03.Reading order

1. Why Reduction Is the Hard Step. Why the obvious method is unusable, and what the alternatives have to beat.
2. Barrett Reduction. Approximating a reciprocal with an integer, worked on ML-KEM's modulus.
3. Montgomery Reduction. Changing representation so that reduction becomes a shift, worked over $\mathbb{F}_{17}$.
4. Plantard Reduction. The 2021 refinement, and why it is an open research opportunity rather than settled practice.
5. Special-Prime Tricks. Why ML-DSA's modulus can be reduced with shifts and adds alone, and ML-KEM's cannot.
6. The Sponge Construction. How one permutation becomes a hash, a stream cipher, and a random oracle.
7. Inside Keccak-f[1600]. The five steps of the permutation, and what each is for.
8. Hardware Footprint, and the Chapter Summary. What all of this costs in silicon, and the chapter summary.

04.A note on what "fast" means here

The earlier chapters counted operations. This one counts something else.

A design that uses fewer multiplications is not automatically faster. What usually decides performance in this material is the critical path, meaning the longest chain of dependent logic between two clock edges, because that sets the clock frequency for the entire design. A method with one extra addition but a shorter dependency chain can be the faster one.

The second thing that decides it is whether the operation is constant-time. Several natural formulations here end with "if the result is too large, subtract $q$", and written as a branch that is a timing side channel on secret data. Every method in this chapter has a branchless form, and the branchless form is the only one that may be used.

Those two constraints, critical path and constant time, explain most of why the published techniques look the way they do.