Appendix D: Solutions for Chapter 16

This page collects solutions and editorial notes for the exercises in Chapter 16: FORS and the stateless hypertree. 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 fors_hypertree package. Its directory in the companion repository is solutions/ch16-fors, and pytest tests/ch16 runs its suite from a clone. Appendix C has the setup.

Exercise 1

The first 3 bytes of SHA256(b"exercise") are extracted and split into six 4-bit groups. Each group is one FORS index in $[0, t-1]$ at $t = 16$. The exact bytes depend on SHA-256, computed below.

import hashlib
digest = hashlib.sha256(b"exercise").digest()
first3 = digest[:3]
bits = "".join(f"{b:08b}" for b in first3)
indices = [int(bits[4 * i:4 * i + 4], 2) for i in range(6)]
print(first3.hex(), bits)
print(indices)
# ==> f55101 111101010101000100000001
# ==> [15, 5, 5, 1, 0, 1]

Exercise 2

Setting $P = 0.5$ in $P \approx q^2 k / (2 t)$ gives $q^2 = t / k$, so the continuous threshold is $q = \sqrt{t / k} = \sqrt{4096 / 14} \approx 17.1$. The first integer at which the approximate bound exceeds $0.5$ is $q = 18$: $17^2 \cdot 14 / 8192 = 0.494 < 0.5 < 0.554 = 18^2 \cdot 14 / 8192$. This is the loose birthday bound on a repeated index draw, not a forgery threshold. A repeated draw re-reveals a leaf the signer already exposed; a forgery needs every one of the $k$ trees to already expose the target’s index (Chapter 16, occupancy analysis). SLH-DSA keeps the per-FORS-instance signature count tiny by deriving the hypertree position from $H_{\text{msg}}$ over a $2^{h}$ position space ($2^{63}$ FORS keypairs for SLH-DSA-128s). Two signatures rarely land on the same instance, and the FORS few-time bound covers the ones that do.

import math
cont = math.sqrt(4096 / 14)
q = 1
while q * q * 14 / (2 * 4096) <= 0.5:
    q += 1
print(round(cont, 2), q)
# ==> 17.1 18

Exercise 3

At $w = 16, n = 32$, each WOTS+ signature is $\ell \cdot n = 67 \cdot 32 = 2144$ bytes, from the Chapter 15 derivation of $\ell$. Each authentication path within a subtree of height $h'$ is $h' \cdot n = 5 \cdot 32 = 160$ bytes.

Per layer: one WOTS+ signature (2144) plus one authentication path (160) = 2304 bytes. With $d = 3$ layers, hypertree signature is $3 \cdot 2304 = 6912$ bytes.

The chain count is derived with integer arithmetic only, matching the chapter and FIPS 205 Algorithm 1. The standard says implementations “shall not use floating-point arithmetic, as rounding errors in floating point operations may lead to incorrect results in some cases”:

n = 32
w = 16
lg_w = w.bit_length() - 1               # w is a power of two
l1 = (8 * n + lg_w - 1) // lg_w         # ceil(8n / lg_w)
max_c = l1 * (w - 1)
l2 = 1
capacity = w
while capacity <= max_c:
    l2 += 1
    capacity *= w
ell = l1 + l2
per_layer = ell * n + 5 * n
print(ell, per_layer, 3 * per_layer)
# ==> 67 2304 6912

Exercise 4

WOTS+ is a one-time signature: signing two distinct messages on the same chain leaks chain values that let an adversary forge any later message hashing into a higher digit at every position. The two-message exposure on a single WOTS+ key is structurally identical to the Lamport two-signature exposure from Chapter 14, just compressed by the base-$w$ chain.

FORS is a few-time signature, and it degrades gradually rather than collapsing at the second message. Two signatures reveal the leaf at each message’s selected index in each of the $k$ trees, so the exposed set grows by at most $k$ values and by fewer when the two messages happen to select the same index. Forgery needs more than an overlap: the target’s index must fall in the already-exposed set of every one of the $k$ trees at once. The chapter’s occupancy form $(1 - (1 - 1/t)^{q})^{k}$ prices that, and at the teaching $k = 6$, $t = 16$ it is still about $0.012$ after ten signatures. The $q^2 k / (2t)$ bound from exercise 2 measures a different event, a repeated draw, which re-reveals a leaf the signer already exposed.

The net effect is where each scheme sits. SLH-DSA pays the FORS bandwidth premium at the message layer, where two messages genuinely differ. It keeps WOTS+ at the inner hypertree layers, where a repeated position makes each inner key re-sign the value it signed before. Those inner inputs (the FORS public key and the lower subtree roots) are fixed by SK.seed and PK.seed, so a position collision exposes no new chain values at all. The whole message-dependent reuse burden lands on FORS, which is built to absorb it.

Exercise 5

Top-down verification would require the verifier to start with the top-tree root (which it has from the public key) and step down through each layer’s WOTS+ signature to obtain the next-layer subtree root. The problem is the direction of the data. At each layer the WOTS+ public key is compressed into a leaf of that layer’s own subtree, and what the layer above signs is that subtree’s root. The verifier recovers the WOTS+ public key from the signature plus the message it signed, and at layer $j$ that message is the root of the layer-$(j-1)$ subtree, which is only available after layer $j-1$ has been verified. Going downward would require the verifier to already have that lower root, and at layer 0 the signed message is what the verifier is trying to authenticate.

Bottom-up verification is the only direction that works: starting from the FORS public key and the message-digest indices, climb up by reconstructing each layer’s subtree root, feeding it as the WOTS+-signed message at the layer above. The hypertree’s structural dependency runs upward in verification, the same direction the signer built it.