Appendix D: Solutions for Chapter 17

This page collects solutions and editorial notes for the exercises in Chapter 17: SLH-DSA (FIPS 205) from scratch. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

The fuller versions of these routines are in the slh_dsa package. Its directory in the companion repository is solutions/ch17-slh-dsa, and pytest tests/ch17 runs its suite from a clone. That suite checks the implementation against the official FIPS 205 ACVP vectors at all twelve parameter sets. Appendix C has the setup.

Exercise 1

The compressed ADRS extracts: byte 3 (low byte of layer address) + bytes 8-15 (low 8 bytes of tree address) + byte 19 (low byte of type) + bytes 20-31 (12 bytes of context-dependent fields). Total: $1 + 8 + 1 + 12 = 22$ bytes.

adrs = bytearray(32)
adrs[3] = 3       # layer address (low byte)
adrs[15] = 100    # tree address (low byte; high bytes 8-14 are zero)
adrs[19] = 0      # type WOTS_HASH
adrs[23] = 7      # keypair address (low byte)
adrs[27] = 12     # chain address (low byte)
adrs[31] = 5      # hash address (low byte)
compressed = bytes([adrs[3]]) + bytes(adrs[8:16]) + bytes([adrs[19]]) + bytes(adrs[20:32])
print(len(compressed), compressed.hex())
# ==> 22 03000000000000006400000000070000000c00000005

Exercise 2

WOTS+: $\ell_1 = \lceil 8 \cdot 24 / \log_2 16 \rceil = 48$, $\ell_1 (w-1) = 720$, $\ell_2 = \lfloor \log_2 720 / 4 \rfloor + 1 = 2 + 1 = 3$, $\ell = 51$.

Subtree height $h' = h / d = 63 / 7 = 9$.

Components in bytes:

• Randomness $R$: $n = 24$
• FORS signature: $k(a + 1) \cdot n = 17 \cdot 15 \cdot 24 = 6120$
• Hypertree: $d \cdot (\ell + h') \cdot n = 7 \cdot (51 + 9) \cdot 24 = 7 \cdot 60 \cdot 24 = 10080$
• Total: $24 + 6120 + 10080 = 16{,}224$ bytes

This matches the published SLH-DSA-SHA2-192s signature size of 16,224 bytes (Table 2 of FIPS 205).

import math
n, h, d, a, k, w = 24, 63, 7, 14, 17, 16
l1 = math.ceil(8 * n / math.log2(w))
l2 = math.floor(math.log2(l1 * (w - 1)) / math.log2(w)) + 1
ell = l1 + l2
h_prime = h // d
fors = k * (a + 1) * n
ht = d * (ell + h_prime) * n
total = n + fors + ht
print(ell, fors, ht, total)
# ==> 51 6120 10080 16224

Exercise 3

ADRS bytes 20-31 hold context-dependent fields whose meaning depends on the type. For type WOTS_HASH the context fields are (keypair address, chain address, hash address); for type FORS_TREE they are (keypair address, tree height, tree index). If set_type writes only its own field, bytes 16 to 19, and leaves bytes 20-31 untouched, a hash call that switches type from WOTS_HASH to FORS_TREE inherits whatever (chain address, hash address) the previous call had, and the new hash interprets those bytes as (tree height, tree index).

A concrete scenario: computing an XMSS node with set_type(TREE) immediately after a WOTS+ public-key compression that left keypair address kp in bytes 20 to 23. FIPS 205 never writes that word for type TREE. It specifies it as padding and relies on the type change to zero it. The resulting address encodes the same logical node as the canonical one but is not byte-identical to it, and which value it carries depends on what the implementation happened to hash last. A verifier that clears, or that walks the tree in a different order, computes a different tweak for the same node and verification fails.

Note what this does not do. The type occupies bytes 16 to 19 and is part of every tweak, so two hash calls of different types can never share an address, and within a type every field the algorithm sets explicitly is always set. The failure is therefore not a collision between two logical contexts but the loss of canonicity. The security proof assumes each hash call has a fixed, well-defined, type-conditioned address. A history-dependent one is outside that model even when no two addresses ever coincide. The practical damage is interoperability, and the theoretical damage is that the domain-separation argument no longer applies.

Exercise 4

The hypertree component is $d \cdot (\ell + h') \cdot n$ with $h' = h / d$. With $n = 16, w = 16$: $\ell_1 = 32$, $\ell_2 = 3$, $\ell = 35$. At $d = 3$ and $h = 9$, $h' = 3$, so per layer the cost is $(35 + 3) \cdot 16 = 608$ bytes, total $3 \cdot 608 = 1824$ bytes.

Halving requires roughly halving $d \cdot (\ell + h')$. The simplest move is reducing $h$ from 9 to 3, which gives $h' = 1$ and shrinks the path component by a factor of 3 while leaving WOTS+ unchanged. New layer cost $= (35 + 1) \cdot 16 = 576$, total $= 1728$, only a marginal saving because WOTS+ dominates. Note that $h$ has to stay a multiple of $d$: SLH-DSA defines $h' = h/d$ and builds each subtree over $2^{h'}$ leaves, so a value like $h = 4$ at $d = 3$ is not a parameter set at all. The real cost of this move is the signing positions: $2^3 = 8$ rather than $2^9 = 512$, which for a few-time FORS at the bottom is the difference between comfortable and immediately reused.

A better move: increase $w$ from 16 to 256, reducing $\ell$ from 35 to roughly 18 (since $\ell$ scales as $1 / \log_2 w$). New per-layer cost $\approx (18 + 3) \cdot 16 = 336$, total $\approx 1008$. The cost: each WOTS+ chain now has $w - 1 = 255$ steps instead of 15, so signing and verification each pay 17x more hash operations per chain. Bandwidth halves, CPU rises by an order of magnitude.

The chosen tradeoff depends on which resource is binding. Embedded firmware signing on cellular networks: pay the CPU. Server signing at QPS: pay the bandwidth.

Exercise 5

Signing cost is the axis that decides this, and it is much larger than the word “slow” suggests. The SPHINCS+ round-3 submission benchmarks its own reference and AVX2 code on one core of a 3.1 GHz Intel Xeon E3-1220 with TurboBoost disabled (Aumasson et al., 2020). Taking the simple instances, which are the ones FIPS 205 approves:

	128s	128f	ratio
Signing, AVX2	645M cycles, 208 ms	33.7M cycles, 10.9 ms	19x
Signing, reference C	2,722M cycles, 878 ms	139M cycles, 44.7 ms	20x
Verification, AVX2	0.86M cycles, 0.28 ms	2.15M cycles, 0.69 ms	0.4x

Two things fall out that the size table alone does not show. Signing s is a fifth of a second, not a few milliseconds. And verification runs the other way: s verifies about 2.5 times faster than f, because f spreads the hypertree over $d = 22$ layers against $d = 7$, and every layer costs the verifier one WOTS+ public key to recompute.

Throughput. One core sustains about 4.8 signatures per second at 128s and about 92 at 128f. The application signs 100 per second in total across 8 replicas, so about 12.5 per second per replica. At 128s that is roughly 2.6 cores per replica doing nothing but signing; at 128f it is about 0.14 of a core. If instead the 100 per second is read as per replica, 128s needs about 21 cores per replica and stops being a candidate at all.

Bandwidth on the verifier side: 7,856 against 17,088 bytes per cellular round trip. Stipulate a usable payload of about 1,400 bytes per packet on a mobile link, which is a typical link maximum transmission unit (MTU) less the transport and network framing it carries: that is 6 packets against 13, so s saves 7 packets per signature. The counts move with the framing actually used, and the ratio does not.

The decision depends on which side is binding, and here the server side is binding on both counts. Choose f. It costs the mobile client 7 extra packets and about 0.4 ms of extra verification, and it saves roughly 2.5 cores per replica. Reverse the recommendation when the signing rate is low enough that CPU stops mattering, which for s means a few signatures per second per core: an offline firmware or certificate signer producing a handful of signatures a day pays the 878 ms once and gives every downstream verifier the smaller, faster-to-check signature. That is the case NIST’s draft SP 800-230 sets are aimed at, and Chapter 17’s aside on them is worth rereading here.

References

Aumasson, J.-P., Bernstein, D. J., Beullens, W., Dobraunig, C., Eichlseder, M., Fluhrer, S., Gazdag, S.-L., Hülsing, A., Kampanakis, P., Kölbl, S., Lange, T., Lauridsen, M. M., Mendel, F., Niederhagen, R., Rechberger, C., Rijneveld, J., Schwabe, P., & Westerbaan, B. (2020). SPHINCS+: Submission to the NIST Post-Quantum Cryptography Standardization Process. NIST PQC Round 3 submission; SPHINCS+ specification v3, 1 October 2020. https://sphincs.org/data/sphincs+-round3-specification.pdf