Appendix D: Solutions for Chapter 18

This page collects solutions and editorial notes for the exercises in Chapter 18: Hash-based signature cryptanalysis. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

Exercise 1

WOTS+ at $n = 20, w = 16$: $\ell_1 = \lceil 160/4 \rceil = 40$. The largest checksum $40 \cdot 15 = 600$ needs $\lfloor \log_2 600 \rfloor + 1 = 10$ bits, so $\ell_2 = \lceil 10/4 \rceil = 3$ and $\ell = 43$.

The target counts follow the chapter’s model: $k \cdot t$ FORS leaf hashes inside one instance’s position space, plus the $d \cdot \ell$ WOTS+ chain values the corresponding hypertree layer reveals. That is $10 \cdot 1024 = 10{,}240$ FORS targets and $5 \cdot 43 = 215$ WOTS+ targets, so $10{,}455$ in total. The multi-target advantage is $\log_2 10{,}455 = 13.4$ bits, subtracted from the $8n = 160$-bit hash output, leaving $146.6$ bits classical. The quantum figure halves what is left rather than subtracting the advantage from $80$: Grover over $N$ marked items in a space of $2^{160}$ costs about $2^{(160 - 13.4)/2}$, so $73.3$ bits.

So this set still clears a 128-bit classical preimage-query target without ADRS, and the reason is headroom rather than a small target population. A 160-bit output against a 128-bit target starts 32 bits clear, and a 13.4-bit reduction does not close that gap. SLH-DSA-SHA2-128s starts with no headroom at all: its output is 128 bits against the same target, so the 15.8-bit reduction in the chapter’s table drops it to 112.2 and it falls short.

A NIST category verdict is a different claim and this arithmetic does not reach it. NIST prices a category as the computational resources an attack needs against a reference problem, under a depth limit and in gate counts, so placing a hypothetical scheme in a category takes the whole construction and a cost analysis of the attack on it, not an idealized query count against one hash (National Institute of Standards and Technology, 2016). What the numbers above establish is the query target, which is what the exercise asks for.

That is not an argument that ADRS is unnecessary here. With ADRS every hash call uses a domain-separating address, so the shared-function amplification disappears whatever the headroom. What remains is the explicit reduction loss carried by the SPHINCS+ parameter search behind the approved sets, not a target count (Aumasson et al., 2020, sec. 7.1.2).

import math
n_bytes, k, t, d, w = 20, 10, 1024, 5, 16
lg_w = int(math.log2(w))
l1 = math.ceil(8 * n_bytes / lg_w)
l2 = math.ceil((math.floor(math.log2(l1 * (w - 1))) + 1) / lg_w)
ell = l1 + l2
fors_targets = k * t
wots_targets = d * ell
total = fors_targets + wots_targets
adv = math.log2(total)
print(l1, l2, ell, fors_targets, wots_targets, total)
# ==> 40 3 43 10240 215 10455
print(round(adv, 1), round(160 - adv, 1), round((160 - adv) / 2, 1))
# ==> 13.4 146.6 73.3

Exercise 2

The chapter’s exact-threshold table answers this directly. The first $q$ whose forgery probability reaches $2^{-64}$ is $q = 20$ for SLH-DSA-128f and $q = 176$ for SLH-DSA-128s, so the ‘s’ set tolerates $176 / 20 = 8.8$ times more reuses.

Working it from the quoted approximation instead is worth doing, because it fails here in exactly the way the chapter warns about. Setting $(q/t)^k = 2^{-64}$ gives $q = t \cdot 2^{-64/k}$, so $64 \cdot 2^{-64/33} = 16.7$ for 128f and $4096 \cdot 2^{-64/14} = 172.3$ for 128s. The 128s figure lands within about 2% of the exact 176. The 128f figure is 17% low, because $(q/t)^k$ assumes $q \ll t$ and 128f has $t = 64$, so $q = 20$ is already a third of the tree. The approximation over-estimates coverage at every $q$, which is why it reaches any threshold sooner and reports the smaller $q$.

The ‘s’ design buys that reuse tolerance with a larger $t$: 4,096 leaves per FORS tree against 128f’s 64. The extra depth is cheap, because the FORS contribution to a signature is $k(a + 1)n$ bytes and $a$ grows only as $\log_2 t$. The ‘f’ design gives the tolerance up for signing speed, spreading its hypertree over 22 layers of height 3 rather than 7 of height 9. It pays for that speed in signature size: 17,088 bytes against 7,856 (National Institute of Standards and Technology, 2024).

import math

def log2_p(q, k, t):
    return k * math.log2(-math.expm1(q * math.log1p(-1.0 / t)))

for name, k, t in (("128f", 33, 64), ("128s", 14, 4096)):
    approx = t * 2 ** (-64 / k)
    exact = next(q for q in range(1, 10_000) if log2_p(q, k, t) >= -64)
    print(f"{name}: exact {exact}, approx {approx:.1f}")
# ==> 128f: exact 20, approx 16.7
# ==> 128s: exact 176, approx 172.3

Exercise 3

The BHT cubic-root collision algorithm is asymptotically faster than Grover, but the constant factors are dominated by the quantum-RAM (QRAM) requirement. BHT needs random access to a stored list of $2^{n/3}$ classically-precomputed images and the ability to query that list in superposition. A QRAM at $n = 128$ would store $2^{42.7}$ entries of 128 bits each, roughly 110 terabytes of classical data that the algorithm must be able to address in superposition (quantum-accessible classical memory), which is not the same as holding the table in quantum registers but is no more available. No physical QRAM at that scale exists or is on any plausible roadmap, and the gate complexity of accessing such a memory in superposition is itself $\Omega(2^{n/3})$ in the standard model. NIST therefore measures Category 1 against the gate-and-qubit-count cost of Grover, not against algorithmic asymptotics that assume QRAM.

$2^{64}$ is the idealized Grover query count for AES-128, not the physical bill. NIST’s own estimate for the Category 1 reference is $2^{170}$/MAXDEPTH quantum gates, or $2^{143}$ classical gates, with the circuit depth capped at MAXDEPTH between $2^{40}$ and $2^{96}$ (National Institute of Standards and Technology, 2016), and it says outright that the categories give substantially more quantum security than the naive $n/2$ suggests. A BHT figure in the query model cannot be compared against that. Its gate and memory costs would have to be priced the same way, and when they are, the collision exponent does not fall to $n/3$. Reducing the floor to BHT’s asymptotic $2^{42.7}$ would treat hardware that does not exist as if it did.

Exercise 4

Total cost is $\sum_i d_i + \sum_i (w - 1 - d_i) = \sum_i (d_i + w - 1 - d_i) = \sum_i (w - 1) = \ell (w - 1)$. The $d_i$ terms cancel exactly. At $w = 16, \ell = 35$: $35 \cdot 15 = 525$ hash evaluations regardless of which digits the message produces.

The cancellation is worth separating from what it buys. Verify-after-sign is a fault countermeasure: it re-derives the public key from the signature it just produced and compares, so a fault that moved a chain value fails the check. The constant total is a property of its cost, not its purpose.

It is not by itself a timing countermeasure. An observer who can separate the signing half from the verification half still sees $\sum_i d_i$, and those digits come from the message digest. The chapter’s timing defence is the other one: walk every chain the full $w - 1$ steps and select the value needed, which pays the same $\ell(w - 1)$ but pays it inside signing. Even that is not full constant-time on its own, as the exercise notes, because the selection and the comparison must also run without data-dependent branching or memory access.

Running the code

The fuller versions of these routines are in the hash_cryptanalysis package under solutions/ch18-hash-cryptanalysis. It carries the parameter table, the signature accounting, the FORS coverage formulas, the generic quantum cost model, and the countermeasure pricing, each as a function rather than as a script. From a clone of the companion repository, pytest tests/ch18 runs its suite. Appendix C has the setup.

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

National Institute of Standards and Technology. (2016). Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. Call for Proposals, Section 4.A.5 (Security Strength Categories). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

National Institute of Standards and Technology. (2024). FIPS 205: Stateless Hash-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.205