Appendix D: Solutions for Chapter 15

This page collects solutions and editorial notes for the exercises in Chapter 15: Many-time signatures. 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 wots_xmss package. Its directory in the companion repository is solutions/ch15-xmss, and pytest tests/ch15 runs its suite from a clone. Appendix C has the setup.

Exercise 1

The WOTS+ parameter formulas are $\ell_1 = \lceil 8n / \log_2 w \rceil$, $\ell_2 = \lfloor \log_2(\ell_1 (w - 1)) / \log_2 w \rfloor + 1$, $\ell = \ell_1 + \ell_2$. Signature size is $\ell \cdot n$ bytes (one chain value per digit).

For $w = 16, n = 24$: $\log_2 w = 4$, $\ell_1 = \lceil 192 / 4 \rceil = 48$, $\ell_1 (w-1) = 720$, $\log_2 720 \approx 9.492$, $\ell_2 = \lfloor 9.492 / 4 \rfloor + 1 = 2 + 1 = 3$, $\ell = 51$. Signature: $51 \cdot 24 = 1224$ bytes.

For $w = 16, n = 32$: $\log_2 w = 4$, $\ell_1 = \lceil 256 / 4 \rceil = 64$, $\ell_1 (w-1) = 960$, $\log_2 960 \approx 9.907$, $\ell_2 = \lfloor 9.907 / 4 \rfloor + 1 = 2 + 1 = 3$, $\ell = 67$. Signature: $67 \cdot 32 = 2144$ bytes.

The size difference is a product of two factors that shrink together, not one dominant factor. At $w = 16$, $\ell_1 = 2n$ and $\ell_2$ stays at 3, so the signature is $(2n + 3) \cdot n = 2n^2 + 3n$ bytes: the number of chains and the number of bytes in each chain value both track $n$. Going from $n = 32$ to $n = 24$ cuts the chain count from 67 to 51, a factor of $0.76$, and each chain value from 32 to 24 bytes, a factor of $0.75$. The two are comparable, and the total falls by roughly their product: $2144 \to 1224$ is a factor of $0.57$. The smaller $n = 24$ signature is not free: $n$ is the hash-output security parameter, so 24 bytes targets roughly NIST Category 3 (192-bit) while 32 bytes targets Category 5 (256-bit). Shrinking the signature trades classical and quantum preimage margin, not just bandwidth.

import math
def wots_params(n, w):
    l1 = math.ceil(8 * n / math.log2(w))
    l2 = math.floor(math.log2(l1 * (w - 1)) / math.log2(w)) + 1
    return l1, l2, l1 + l2, (l1 + l2) * n


print(wots_params(24, 16))
print(wots_params(32, 16))
# ==> (48, 3, 51, 1224)
# ==> (64, 3, 67, 2144)

Exercise 2

The chain function $F$ is one-way, so given the chain value at position 9 the adversary can hash forward two more steps to obtain the chain value at position 11. That is the message-chain forgery for digit $d_3 = 11$. Two forward hashes is the only operation needed for the message-chain step.

The checksum $C = \sum_i (w - 1 - d_i)$ is signed in the same chain structure as the message digits. Increasing $d_3$ from 9 to 11 decreases the checksum contribution from position 3 by 2, so the checksum $C$ drops by 2 and its base-16 digits change. A smaller number in base $w$ has at least one strictly smaller digit, so at least one checksum chain must move backward by at least one step, though not necessarily two on one chain: if $C$ was $\mathtt{0x1c0}$ the digits go from $(1, 12, 0)$ to $(1, 11, 14)$, one chain back by one and another forward by fourteen. Moving forward is free. Moving backward means inverting $F$ on that chain, and that is what stops the forgery. The forgery breaks because increasing message digits decreases the checksum, and producing chain values at lower positions is exactly what the one-way property prevents.

Exercise 3

L-tree levels for input count 5:

• Level 0: 5 values $V_0, V_1, V_2, V_3, V_4$. Pair $(V_0, V_1)$ and $(V_2, V_3)$, hash each pair. $V_4$ has no sibling so it is promoted unchanged. Result: 3 nodes $N_0, N_1, V_4$. Hashes used: 2.
• Level 1: 3 values. Pair $(N_0, N_1)$, hash. Promote $V_4$. Result: 2 nodes. Hashes used: 1.
• Level 2: 2 values. Pair them, hash. Result: 1 node (the root). Hashes used: 1.

Total: $2 + 1 + 1 = 4$ hash evaluations to compute the L-tree root from 5 inputs.

Exercise 4

$2^{20} = 1{,}048{,}576$ signatures total. At 100 per day, the key lasts $1{,}048{,}576 / 100 \approx 10{,}486$ days, about 28.7 years.

A weekly backup that is restored after a crash rewinds the leaf-index counter by up to seven days of signing (700 signatures at the average rate). Resuming from the restored counter would reuse leaf indices that were already consumed in the interval between backup and crash. Reusing a WOTS+ leaf is catastrophic. The second signature on a different message reveals, at every chain, the lower of the two signed digits and everything above it, so any message whose 67 digits (checksum included) all sit at or above those minima can be signed by hashing forward.

That is not every message. At $w = 16$ the 64 message digits alone admit a random digest with probability around $2^{-33}$ to $2^{-50}$, depending on the two digests signed, and the three checksum chains cut it further: a digest whose message digits all sit high has a small checksum, so its checksum digits tend to fall below the signed minima. Over typical pairs the full 67-digit condition is met by about one digest in $2^{60}$, with wide variation either way. That is still a break, because an adversary who chooses the message finds a qualifying one by searching that many candidates, far inside the $2^{128}$ the parameters promise, so the one-time property is gone even though the forgery is not universal. Chapter 15’s leaf-reuse section and Chapter 14’s two-signature analysis give the same picture: each signature exposes more of the key and the forgeable set grows.

SP 800-208 addresses this at the module boundary rather than at the backup procedure. Section 8.1 requires key and signature generation to run in a hardware cryptographic module validated to FIPS 140-2 or FIPS 140-3 Level 3 or higher physical security. That module “shall not allow for the export of private keying material”. A restorable copy of the private key is therefore not something a conforming deployment can make, and that is what removes the two-machines-one-counter hazard. The same section requires the module to increment the leaf index and store it in nonvolatile storage “before exporting a signature value or accepting another request to sign a message”. A crash after signing loses the signature rather than the counter advance. Section 9.1 adds a design suggestion rather than a requirement: where a hardware module implements a monotonic counter, using its current value to select the one-time key “may be very helpful in avoiding unintentional reuse”.

total = 2 ** 20
per_day = 100
print(total, round(total / per_day), round(total / per_day / 365, 1))
# ==> 1048576 10486 28.7

Exercise 5

XMSS signature components at $w = 16, n = 32, h = 20$ (the exercise writes the XMSS tree height as $h$ and the Merkle depth as $d$, both 20 here):

• Leaf index: 4 bytes (32-bit counter).
• Randomness $r$: 32 bytes ($n$).
• WOTS+ signature: $\ell \cdot n = 67 \cdot 32 = 2144$ bytes.
• Authentication path: $h$ siblings of $n$ bytes each $= 20 \cdot 32 = 640$ bytes.
• Total: $4 + 32 + 2144 + 640 = 2820$ bytes.

Lamport + Merkle at $d = 20, n = 32$, serialized as Chapter 14 does: the Lamport signature is $256 \cdot n = 8192$ bytes (one secret per digest bit), the Lamport public key the verifier needs is $2 \cdot 256 \cdot n = 16384$ bytes, and the authentication path adds $20 \cdot 32 = 640$ bytes. Total: $8192 + 16384 + 640 = 25{,}216$ bytes, Chapter 14’s own figure.

XMSS at $w = 16$ produces signatures roughly 8.9x smaller than Chapter 14’s Lamport + Merkle at the same depth. About 3.8x of that is WOTS+‘s base-$w$ chain compression (2,144 against 8,192 bytes for the one-time signature alone). The rest is that an XMSS verifier recomputes the WOTS+ public key from the signature, where Chapter 14’s verifier has to be sent the Lamport public key. The CPU cost is correspondingly higher (each WOTS+ signature requires up to $\ell (w-1) = 1005$ hash evaluations versus Lamport’s $\sim 256$ hashes for the public-key reconstruction), but for any device that pays per byte (cellular, LoRa, on-chain) WOTS+ wins decisively.

xmss = 4 + 32 + 67 * 32 + 20 * 32
lamport = 256 * 32 + 2 * 256 * 32 + 20 * 32
print(xmss, lamport, round(lamport / xmss, 2))
# ==> 2820 25216 8.94