Exercises

01.1. Barrett for the signature modulus

Take $q = 8380417$ and $k = 48$. Compute $m = \lfloor 2^{48}/q \rfloor$ and check that Barrett leaves $r \in [0, 2q)$ after step B3.

Answer.

$$m \;=\; \left\lfloor \frac{2^{48}}{8380417} \right\rfloor \;=\; 33587228 .$$

The choice $k = 48$ satisfies $2^k > q^2$, since $q^2 \approx 7.02 \times 10^{13}$ and $2^{48} \approx 2.81 \times 10^{14}$.

Sampling 5000 random inputs from $[0, q^2)$ and running steps B1 to B3 gives $r \in [0, 2q)$ every time, with zero violations, so one conditional subtraction in B4 always suffices.

Worth contrasting with the constant in Barrett Reduction. There the manuscript's $m$ was one too large and the bound failed on some inputs. Here the constant is derived correctly and the bound holds. Same algorithm, and the difference between working and subtly broken is one unit in a precomputed integer.

02.2. A Montgomery round trip at real parameters

For $q = 3329$ and $R = 2^{16}$, find $q'$, put $x = 2048$ into Montgomery form, square it, reduce, convert back, and compare with $x^2 \bmod q$.

Answer. Solving $q q' \equiv -1 \pmod{2^{16}}$ gives

$$q' \;=\; 3327, \qquad \text{since } 3329 \times 3327 \bmod 65536 = 65535 = R - 1 .$$

Convert: $\tilde{x} = 2048 \times 65536 \bmod 3329 = 2435$.

Square in the Montgomery domain: $T = 2435^2 = 5929225$, and one Montgomery reduction gives $38$.

Convert back with a second reduction of $T = 38$: the result is $3093$.

Check directly: $2048^2 = 4194304$, and $4194304 \bmod 3329 = 3093$. They agree.

Notice that the intermediate $38$ is meaningless on its own. It is $x^2 R \bmod q$, which is the Montgomery form of the answer, and reading it as an ordinary residue would be wrong. That is the standard trap when debugging this code: values in the middle of a transform are not the numbers they look like.

03.3. Solinas reduction, written out

Show that $q = 2^{23} - 2^{13} + 1$ reduces any $x \in [0, 2^{46})$ using shifts and adds only. How many conditional subtractions finish it?

Answer. Split $x = x_H \cdot 2^{23} + x_L$ with both parts below $2^{23}$. Since $2^{23} \equiv 2^{13} - 1 \pmod q$,

$$x \;\equiv\; x_L \;+\; (x_H \ll 13) \;-\; x_H \pmod q .$$

That is one shift, one addition and one subtraction.

Bounding the result: $x_L < 2^{23}$ and $x_H \ll 13 < 2^{36}$, so the fold can reach about $2^{36}$, which is far above $q \approx 2^{23}$. One pass is not enough.

Apply the same fold again to the result. Each pass roughly replaces a value of magnitude $2^a$ with one of magnitude $2^{a-10}$, since the high part shrinks by 23 bits and grows back by 13. Starting just below $2^{46}$, the passes measure out as $2^{36}$, then $2^{27}$, then $2^{24}$, at which point the value sits at about $1.01 \times q$.

From there one or two conditional subtractions land it in $[0, q)$. So the whole reduction is three folds and at most two conditional subtractions, all shifts, adds and compares, and no multiplication at any point.

The worked example in Special-Prime Tricks shows a single fold taking $12{,}345{,}678{,}901$ to $18{,}085{,}494$, which is $2.16 \times q$ and therefore needs exactly two more subtractions.

04.4. Counting SHAKE calls

For ML-KEM-768, how many SHAKE128 permutations does expanding $A$ take, assuming 672 bytes per ring element? Compare with the SHAKE256 budget for sampling $\mathbf{s}$ and $\mathbf{e}$.

Answer. The matrix has $k^2 = 9$ ring elements, so $9 \times 672 = 6048$ bytes. SHAKE128 has rate 1344 bits, which is 168 bytes per permutation, giving

$$6048 / 168 \;=\; 36 \text{ permutations}.$$

For the secrets, each of $\mathbf{s}$ and $\mathbf{e}$ needs $k \cdot n \cdot \eta_1 / 4 = 3 \times 256 \times 2 / 4 = 384$ bytes, so $768$ bytes together. SHAKE256 has rate 1088 bits, which is 136 bytes, giving

$$\lceil 768 / 136 \rceil \;=\; 6 \text{ permutations}.$$

So matrix expansion costs six times as much hashing as secret sampling, which is why SHAKE128 with its higher rate is used there and SHAKE256 with its stronger capacity is reserved for the secrets. The choice in The Sponge Construction is a throughput decision, and this is the arithmetic behind it.

The 672 bytes per ring element is itself a consequence of rejection sampling: 256 coefficients need 384 bytes of 12-bit values if nothing is rejected, and roughly one candidate in five is discarded, so the budget is padded.

05.5. Gate count for one Keccak round

Answer. Counting XORs per round on the 1600-bit state.

$\theta$: five column parities, each four XORs on 64-bit lanes, so $5 \times 4 \times 64 = 1280$. Then $D$ is one XOR per column, $5 \times 64 = 320$. Then $D$ is XORed into all 25 lanes, $25 \times 64 = 1600$. Total about $3200$.

$\rho$ and $\pi$: zero gates. Both are fixed rewiring.

$\chi$: per output bit, one NOT, one AND and one XOR, so $1600$ XORs and $1600$ ANDs.

$\iota$: 64 XORs, and only on lane $(0,0)$.

So roughly $4900$ XOR gates and $1600$ AND gates per round.

For a one-round-per-cycle datapath, add 1600 flip-flops for the state. At a rough two to four LUTs per gate-equivalent on an FPGA, that lands in the fifteen to twenty thousand LUT range quoted in Hardware Footprint, and the Chapter Summary, which is the consistency check worth making.

The ratio is the interesting part. Three quarters of the logic is $\theta$, the diffusion layer, and the single non-linear step is a sixth of it. Keccak is cheap because non-linearity is cheap here.

06.6. Reduction for a unified engine

Argue which reduction method you would use for each modulus in a design serving both standards, and whether one datapath can cover both.

Answer. There is no single right answer, and the exercise is to commit to one and be able to defend it.

For ML-DSA, the Solinas fold from Special-Prime Tricks is hard to argue against. It needs no multiplier at all, so it is strictly cheaper than any general method in both area and latency. Any design not using it is leaving free performance behind.

For ML-KEM, the choice is between Montgomery and Plantard. Montgomery is proven, widely implemented and well understood. Plantard offers ten to twenty percent more clock frequency on current FPGA fabric and is under-represented in the literature. For a research design where the point is to explore, Plantard is the more interesting commitment.

Can one datapath cover both? Not the reduction tail. A shift-and-add network for a 23-bit Solinas prime and a multiplier-based reducer for a 12-bit generic prime are different circuits, not one circuit with a mode bit. A unified design either instantiates both and multiplexes, paying area for whichever is idle, or gives up the Solinas advantage and uses the general method for both.

The first architectural decision to commit to is therefore the one above the reduction: whether the butterfly datapath is parameterised by coefficient width. If it is, then two reduction tails behind a shared butterfly is a coherent design. If not, the two schemes get separate engines and the only sharing is the Keccak block.

07.7. Break the naive padding

Show that appending zeros instead of pad10*1 allows a collision, and construct one.

Answer. With a zero-fill rule, any input and that same input followed by zero bytes pad to the identical block sequence.

Take SHAKE128, whose rate is 168 bytes. The input "abc" pads to "abc" followed by 165 zero bytes. The input "abc" followed by a single zero byte pads to "abc", one zero byte, and 164 more zero bytes.

Both produce exactly the same 168-byte block, so both absorb identically and squeeze identical output. Two distinct inputs, one output. A collision found by inspection, with no computation at all.

The pad10*1 rule stops this because the terminating $1$ bit lands at a position determined by the input length. The two inputs above differ in length by one byte, so their terminators fall in different places, and the padded blocks differ.

This is why the padding rule is part of the specification rather than an implementation detail, and why the domain byte from The Sponge Construction rides along with it.