Appendix D: Solutions for Chapter 14

This page collects solutions and editorial notes for the exercises in Chapter 14: One-time signatures from hash functions. 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 lamport_merkle package. Its directory in the companion repository is solutions/ch14-lamport, and pytest tests/ch14 runs its suite from a clone. Appendix C has the setup.

Exercise 1

The Lamport scheme signs the SHA-256 digest of the message, not the raw bytes: hashlib.sha256(b"\x5C").digest() begins with the byte 0xa9, so the bit string is 10101001 (MSB to LSB at positions 0-7). The signer reveals secret $s_{i, b_i}$ at every position $i$ where $b_i$ is that digest bit. The verifier hashes each revealed secret and compares to the corresponding public-key half $h(s_{i, b_i})$. The structural answer: exactly 8 secrets are revealed (one per bit) and exactly 8 hash comparisons verify the signature. The exact secret bytes depend on how the seed is expanded; the verification logic is independent of that expansion.

Exercise 2

For two distinct messages $m_1, m_2$ with digests $h_1, h_2$, the adversary observes secret $s_{i, b_1[i]}$ for each bit $i$ of $h_1$ and $s_{i, b_2[i]}$ for each bit of $h_2$. At every position $i$ where $h_1[i] \ne h_2[i]$ the adversary holds both halves of the secret pair. The expected Hamming distance between two random 256-bit digests is 128. Here b"alpha" and b"beta" give 133, so 133 positions leak both halves and the remaining 123 leak one. The five lowest such positions are $i = 1, 2, 3, 4, 6$.

For target $m^*$ with digest $h_3$, position $i$ is forgeable iff $s_{i, h_3[i]}$ has been observed, which happens iff $h_1[i] = h_3[i]$ or $h_2[i] = h_3[i]$. At the 133 both-halves positions that is certain. At the other 123 it holds with probability $1/2$, so the conditional expectation is $133 + 123/2 = 194.5$. For the target b"gamma" the measured count is 189 of 256, leaving 67 positions whose secret the adversary cannot supply.

Two framings of “how unlikely is a full forgery” appear across this chapter, and they answer different questions. Conditioned on an observed Hamming distance $h$, a random third digest is forgeable at every position with probability $(1/2)^{256-h}$, which is the $2^{-124}$ the chapter quotes at $h = 132$. Averaged over all three digests instead, each position is forgeable with probability $1 - 1/4 = 3/4$, giving $(3/4)^{256} \approx 2^{-106}$. Both say the same thing: two signatures expose structure without yielding a complete signature on a random target.

import hashlib

def bit(digest, i):
    return (digest[i // 8] >> (7 - (i % 8))) & 1

h1 = hashlib.sha256(b"alpha").digest()
h2 = hashlib.sha256(b"beta").digest()
h3 = hashlib.sha256(b"gamma").digest()

hamming = sum(bin(a ^ b).count("1") for a, b in zip(h1, h2))
print(hamming)
# ==> 133

# A position leaks both halves when the two signed digests disagree there.
known = [{bit(h1, i), bit(h2, i)} for i in range(256)]
print([i for i in range(256) if len(known[i]) == 2][:5])
# ==> [1, 2, 3, 4, 6]

print(sum(1 for i in range(256) if bit(h3, i) in known[i]))
# ==> 189

Exercise 3

The tree at depth 3 has 8 leaves, 4 nodes at level 1, 2 at level 2, 1 root. The authentication path for leaf 5 (binary 101) is the sibling at each level: leaf 4, node-pair-(6,7), and node-pair-(0..3). Verification: hash leaf 5, combine with the level-0 sibling, then iterate up.

import hashlib

def H(*args):
    h = hashlib.sha256()
    for a in args:
        h.update(a)
    return h.digest()


leaves = [H(f"ex3-leaf-{i}".encode()) for i in range(8)]
level1 = [H(leaves[2 * i], leaves[2 * i + 1]) for i in range(4)]
level2 = [H(level1[2 * i], level1[2 * i + 1]) for i in range(2)]
root = H(level2[0], level2[1])

# Authentication path for leaf 5 (right child in pair (4, 5))
auth = [leaves[4], level1[3], level2[0]]
node = H(auth[0], leaves[5])      # combine sibling left || self right
node = H(node, auth[1])           # pair (4, 5) is left at level 2; sibling is right
node = H(auth[2], node)           # this subtree was right at top; sibling is left
print(root.hex()[:8])
print(node == root)
# ==> de559961
# ==> True

Exercise 4

NIST defines categories 1, 3, and 5 by the computational resources of key search on AES-128, AES-192, and AES-256, and prices those references as gate counts under a depth limit: $2^{170} / \mathrm{MAXDEPTH}$, $2^{233} / \mathrm{MAXDEPTH}$, and $2^{298} / \mathrm{MAXDEPTH}$ quantum gates (National Institute of Standards and Technology, 2016). In the idealized serial-query model, Grover’s key search on a $k$-bit key costs $2^{k/2}$ queries and a preimage search on an $n$-bit hash costs $2^{n/2}$, so a hash pairs with the AES key of the same length by query count alone. That pairing is what the last column records. It is not a category claim, because the table costs no circuits. The chapter’s table under “Grover’s impact on hash preimage security” draws the same line.

$n$	classical $2^n$	quantum $2^{n/2}$	AES analogue (query model)
128	$2^{128}$	$2^{64}$	equal to AES-128 ($2^{64}$)
160	$2^{160}$	$2^{80}$	between AES-128 ($2^{64}$) and AES-192 ($2^{96}$)
192	$2^{192}$	$2^{96}$	equal to AES-192 ($2^{96}$)
224	$2^{224}$	$2^{112}$	between AES-192 ($2^{96}$) and AES-256 ($2^{128}$)
256	$2^{256}$	$2^{128}$	equal to AES-256 ($2^{128}$)
384	$2^{384}$	$2^{192}$	above AES-256
512	$2^{512}$	$2^{256}$	above AES-256

In query counts, $n = 128$, $192$, and $256$ equal AES-128, AES-192, and AES-256 in turn. The outputs $n = 160$ and $n = 224$ sit strictly between two adjacent key lengths, and $n \ge 384$ exceeds AES-256. Reading a row as “meets category 1” needs two things the table does not supply: the gate count of the hash oracle inside the Grover circuit, and the depth limit it runs under. That is how NIST prices the AES references, and it is what Jaques et al. cost for AES itself (Jaques et al., 2020). SHA-256’s $2^{128}$ quantum preimage query count equals AES-256’s key-search query count. Whether a SHA-256 preimage circuit costs more or fewer than $2^{298} / \mathrm{MAXDEPTH}$ gates is a circuit question this table does not answer.

References

Jaques, S., Naehrig, M., Roetteler, M., & Virdia, F. (2020). Implementing Grover oracles for quantum key search on AES and LowMC. Advances in Cryptology – EUROCRYPT 2020. https://doi.org/10.1007/978-3-030-45724-2_10

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