Appendix D: Solutions for Chapter 32

This page collects solutions and editorial notes for the exercises in Chapter 32: PQ-secure commitment schemes. 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 commitment_schemes package under solutions/ch32-commitment-schemes. From a clone of the companion repository, pytest tests/ch32 runs its suite. Appendix C has the setup.

Exercise 1

For an $n$ -bit hash:

BHT (Brassard-Hoyer-Tapp 1998) collision bound: $2^{n/3}$ quantum evaluations, assuming quantum random access to a classical memory (QRACM) holding about $2^{n/3}$ entries.
CNPS (Chailloux-Naya-Plasencia-Schrottenloher 2017) collision bound: $2^{2n/5}$ time without QRACM, using only polynomial quantum memory and about $2^{n/5}$ classical memory.

For $n = 160$ (BLAKE2s at 160-bit output, the ethSTARK suggested 80-bit setting): BHT gives $2^{53.3}$ , CNPS gives $2^{64.0}$ .

Adequacy assessment:

(a) 80-bit BHT margin. $2^{53.3}$ falls short of $2^{80}$ by 26.7 bits. Inadequate: a BHT-capable adversary can find a Merkle collision well inside the 80-bit security budget.
(b) 80-bit CNPS margin. $2^{64.0}$ falls short of $2^{80}$ by 16 bits. Inadequate even under the no-QRACM model.
(c) 128-bit PQ margin. BHT ( $2^{53.3}$ ) falls short by 74.7 bits; CNPS ( $2^{64.0}$ ) falls short by 64 bits. Far from the 128-bit PQ margin in either model.

Minimum output widths:

80-bit BHT margin: $n \ge 240$ bits ( $2^{80} \le 2^{n/3}$ ).
80-bit CNPS margin: $n \ge 200$ bits ( $2^{80} \le 2^{2n/5}$ ).
128-bit BHT margin: $n \ge 384$ bits ( $2^{128} \le 2^{n/3}$ ).
128-bit CNPS margin: $n \ge 320$ bits ( $2^{128} \le 2^{2n/5}$ ).

The ethSTARK 160-bit BLAKE2s choice follows the document’s own rule that the digest be at least twice the target, an 80-bit classical target in the random-oracle model with the grinding (proof-of-work) bits counted, not an 80-bit quantum collision-resistance target on the Merkle hash itself. The gap above is the gap a PQ-aware reparameterization would close. Widening the hash is the reparameterization, and the widths above say how far it has to go. A 256-bit output supplies about 85.3 bits under BHT and 102.4 under CNPS, so it is wider than the 160-bit setting without meeting the 128-bit collision target. Meeting that target takes 320 bits under CNPS and 384 bits under both. Which production pipeline has adopted which width is a deployment claim that needs the deployment and its date, and this solution makes none.

for n in (160, 200, 240, 256, 320, 384):
    bht = n / 3
    cnps = 2 * n / 5
    print(n, round(bht, 1), round(cnps, 1))
# ==> 160 53.3 64.0
# ==> 200 66.7 80.0
# ==> 240 80.0 96.0
# ==> 256 85.3 102.4
# ==> 320 106.7 128.0
# ==> 384 128.0 153.6

Exercise 2

The exercise simulates the Shor break with brute force at small parameters. For $p = 2027$ , the safe-prime structure means $p - 1 = 2 \cdot 1013$ with $1013$ prime. The subgroup of order $1013$ generated by $g = 2^{(p-1)/1013} \bmod p$ is where the SRS lives. Brute-force search for $\tau$ : enumerate $i \in [1, 1013)$ and find $i$ such that $g^i \equiv g^\tau \pmod p$ . Once $\tau$ is recovered, forge_opening constructs $W_{\text{fake}}$ algebraically: given a target evaluation claim $y_{\text{fake}} = 42$ at $z = 100$ , $W_{\text{fake}} = (C \cdot g^{-y_{\text{fake}}})^{(\tau - z)^{-1} \bmod 1013}$ where $C$ is the commitment, equivalently $g^{(p(\tau) - y_{\text{fake}})/(\tau - z)}$ using the scalar $p(\tau)$ ; $z \ne \tau$ , so the inverse exists. The verifier’s pairing equation $W^{\tau - z} = C \cdot g^{-y}$ is satisfied by construction since the forger computed $W$ from the equation. The exercise demonstrates that recovering $\tau$ trivially forges any opening. KZG’s evaluation binding is proved under the $t$ -strong Diffie-Hellman assumption (Kate et al., 2010), which a discrete-log solver breaks; recovering $\tau$ is therefore sufficient to forge, and the exercise shows that direction only.

Exercise 3

Editorial note. The exercise is a literature-survey check, so the answer moves with the reader’s date. What the five abstracts said on 13 August 2026:

(a) Lowest univariate proof size at 128-bit PQ. Greyhound, at 53 KB for degree at most $2^{30}$ , with its concrete sizes set to reach a security level of about 128 bits. Among the five papers this exercise names, none claims a smaller univariate figure at that degree bound, so Greyhound is still the anchor rather than a superseded baseline.
(b) Lowest multilinear proof size at the same target. Hachi, at approximately 55 KB for a 30-variable polynomial. Note the direction: that is slightly larger than Greyhound’s univariate figure, not smaller. A reader who assumes the newer paper wins on every axis gets this one backwards.
(c) Lowest verifier time at 128-bit PQ. Hachi, by its own comparison table: an asymptotic $\tilde{O}(\lambda)$ improvement over Greyhound, which it puts at 2.8 seconds down to 227 milliseconds. The two wall-clock numbers do not share a measurement: Hachi’s 227 milliseconds is a first-round timing of 96.5 milliseconds on a Mac Mini M4 plus a 130 millisecond estimate for the Greyhound stage from a private communication, and Greyhound’s 2.8 seconds is a whole-verifier time on an AVX-512 Xeon. The asymptotic improvement is the answer. The timings are not a like-for-like comparison.

Two traps sit in the exercise. Jindo does report proof size: it is one of the three metrics in the abstract and one of the three panels of its Table 1. But it is not the size winner, and its own table says so. At $\log N = 20$ that table gives zk-Jindo 1,207 KB against Greyhound’s 46 KB, and Jindo’s smallest entry, 315 KB at $\log N = 14$ , is still an order of magnitude above Greyhound. Jindo optimizes client-side proving instead: its headline is about an order of magnitude over CELPC across proof generation, verification, and size together, its evaluation protocol is built for multilinear polynomials, and its figures carry evaluation hiding where Greyhound’s do not. A reader who reaches for the newest lattice polynomial commitment scheme on question (a) picks it for the wrong axis.

The second trap is HyperWolf, withdrawn from the eprint archive on 3 October 2025. The live paper is Serval, whose own eprint note calls it an optimization of the same work. Its abstract headlines $L = 2^{20}$ , but its own table also places Greyhound beside it at $L = 2^{25}$ and $L = 2^{30}$ , so the comparison with (a) is in the paper. Those sizes are computed from proof-size formulas rather than measured, and its verifier comparison is in ring operations rather than wall-clock time.

Cite the paper’s claimed value, name the parameter set, and date-stamp it. The three answers above are pinned to abstracts read on one day, which is the habit the exercise exists to build.

Exercise 4

Binius belongs to the Merkle family. The commitment is a Merkle root over the codeword of a multilinear polynomial. Binding rests on the collision resistance of the Merkle hash, which is exactly the Merkle-family security argument. The binary-field tower changes the field arithmetic but not the commitment structure. Binary fields make the hashing and the Reed-Solomon encoding cheap, but the prover still produces a Merkle root and the verifier still queries Merkle paths.

Quantum posture: same as any Merkle commitment. The hash needs $3n$ -bit output for $n$ -bit BHT collision security, since BHT gives a $2^{n/3}$ -query collision attack in the quantum-accessible-memory model. The $2n$ relation is the classical birthday one and understates the requirement by a third. Binius’s choice of hash function determines the concrete margin, and at the 128-bit PQ target the same 384-bit floor applies that Exercise 1 derives. A pipeline that runs a FRI-style proximity test above the commitment raises a separate soundness question, and it is a question about the test rather than about the commitment. The two are worth keeping apart: a low-degree extension is an encoding step that evaluates a polynomial on a larger domain, and FRI is the interactive test that a committed word is close to that code. Ch 34 develops FRI soundness over a prime field and does not treat Binius, so no Binius-specific accounting is available in this book. The commitment itself classifies as Merkle either way, which is what the exercise asks.

References

Kate, A., Zaverucha, G. M., & Goldberg, I. (2010). Constant-Size Commitments to Polynomials and Their Applications. In Advances in Cryptology — ASIACRYPT 2010 (Vol. 6477, pp. 177–194). Springer. https://doi.org/10.1007/978-3-642-17373-8_11