Appendix D: Solutions for Chapter 33

This page collects solutions and editorial notes for the exercises in Chapter 33: Fiat-Shamir in the QROM. 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 fiat_shamir_qrom package under solutions/ch33-fiat-shamir-qrom. From a clone of the companion repository, pytest tests/ch33 runs its suite. Appendix C has the setup.

Exercise 1

The chapter’s DFMS20-shaped model: $\varepsilon_{\text{qrom}} \le (2q + 1)^{2r} \cdot \varepsilon_{\text{interactive}}$, the corollary’s coefficient rounded and its additive challenge-space term dropped. Chapter 33 records that the dropped term is about $2^{1771}$ at these parameters, so every width below is an output of the model and not a certified minimum.

With $q = 2^{80}$, $(2q + 1)^{2r} \approx 2^{2r(80+1)} = 2^{2 \cdot 12 \cdot 81} = 2^{1944}$. And $\varepsilon_{\text{interactive}} = (|C|)^{-r} = 2^{-128 \cdot 12} = 2^{-1536}$. The bound gives $\varepsilon_{\text{qrom}} \le 2^{1944 - 1536} = 2^{408}$, vastly greater than 1. A bound greater than 1 says only that the soundness error is at most a probability, which is true by definition. In that regime the bound carries no information and is vacuous.

To meet $\varepsilon_{\text{qrom}} \le 2^{-128}$, we need $(2q+1)^{2r} / |C|^r \le 2^{-128}$, i.e. $|C|^r \ge (2q+1)^{2r} \cdot 2^{128}$, so $|C| \ge (2q+1)^2 \cdot 2^{128/r}$. With $q = 2^{80}$, $(2q+1)^2$ is strictly greater than $2^{162}$ (by the tiny $\log_2(1 + 2^{-81})$ term). With $r = 12$, $128/12 \approx 10.667$. Thus the minimum real $|C|$ has $\log_2 |C| \approx 162.0 + 10.667 \approx 172.67$, and the smallest integer (or power-of-two) bit width that satisfies the strict inequality is 173.

So the per-round challenge space must grow from $2^{128}$ to at least $2^{173}$. The current $|C| = 2^{128}$ is inadequate by 45 bits at the 128-bit PQ target.

import math
r, q_bits, k = 12, 80, 128
loss_bits = 2 * r * (q_bits + 1)          # (2q + 1)^{2r}, approximated
interactive_bits = -128 * r               # eps_interactive = |C|^{-r}
needed = math.ceil(2 * math.log2(2 * 2 ** q_bits + 1) + k / r)
print(loss_bits, interactive_bits, loss_bits + interactive_bits)
print(needed, needed - 128)
# ==> 1944 -1536 408
# ==> 173 45

Exercise 2

Plonky3’s Fiat-Shamir structure compiles two distinct interactions:

• Inner-layer FRI: placed in the proof-of-proximity tier. The Fiat-Shamir compilation here turns each FRI round’s verifier challenge into a hash of the transcript so far. The DFMS20-style reduction loss for FRI is per-round, with the bound dominated by the number of FRI rounds ($\log_2 d$ for a degree bound $d$, so $\log_2 N - \log_2(1/\rho)$ at rate $\rho$ on a low-degree-extension (LDE) domain of size $N$).
• Outer-layer polynomial commitment interface: placed in the polynomial-IOP tier. Plonky3’s commitment scheme (Merkle-FRI in the default configuration) is itself a Fiat-Shamir-compiled interactive proof. The polynomial-IOP layer compiles its rounds with a separate Fiat-Shamir transformation that consumes the inner-layer FRI’s output as one of its messages.

The two tiers are alternative ways for a false statement to be accepted, not two events that must both happen, so the interactive error adds: $\varepsilon_{\text{int}} \le \varepsilon_{\text{IOP}} + \varepsilon_{\text{FRI}} + \varepsilon_{\text{bind}}$, a union bound over the polynomial-IOP check being fooled, the proximity test being fooled, and a Merkle opening being forged. The chapter’s stipulated model then multiplies that sum once, over the compiled protocol’s total round count: $\varepsilon_{\text{qrom}} \le (2q + 1)^{2 (r_{\text{IOP}} + r_{\text{FRI}})} \cdot \varepsilon_{\text{int}}$. That inequality is the model’s and not DFMS20’s Corollary 13, which carries a different coefficient and an additive challenge-space term the model drops, so it is not a certified bound for Plonky3 or for any FRI pipeline. A product $\varepsilon_{\text{IOP}} \cdot \varepsilon_{\text{FRI}}$ would make a perfect proximity test erase the IOP’s own error, which is false. The exponent is why production STARK pipelines minimize the total round count as a first-order design constraint alongside per-round challenge size. Chapter 34 Section 5.5 carries the same partition.

Exercise 3

The classical rewinder runs the prover twice with the same first message $a = g^k$ and different challenges $e_1 \ne e_2$. That yields $z_1 = k + e_1 x$ and $z_2 = k + e_2 x$, from which $x = (z_1 - z_2) / (e_1 - e_2) \bmod n$. The step that fails under quantum queries is the oracle-side fork. The rewinder needs the prover’s decisive query to $H$ in order to answer it differently on the second run. A quantum prover’s queries are in superposition, so finding that query means measuring it, and the measurement disturbs the state the second run would start from. Rewinding itself does have a quantum analogue: DFMS19’s extractor for the sigma protocol measures the response and rewinds on the measured state, with quantum computationally unique responses bounding the disturbance (Theorem 25). What has no direct quantum analogue is the classical extractor’s record-and-replay of oracle queries, which measure-and-reprogram replaces (Don et al., 2019).

Exercise 4

The exercise assumes an interactive soundness error $\varepsilon = 1/|C|$ holding against quantum dishonest provers, so the bound $(2q + 1)^2 \cdot \varepsilon$ reads $(2q + 1)^2 / |C|$. That assumption is the premise, not a consequence of Schnorr’s special soundness: the interactive prover the reduction produces is itself quantum, and DFMS19 records that special soundness does not imply ordinary soundness in the quantum setting (Don et al., 2019). Schnorr supplies the transcript algebra here and nothing more. At $q = 2^{16}$ and $|C| = 1013 \approx 2^{9.985}$ that is $\approx 2^{34} / 2^{9.985} \approx 2^{24}$, vastly larger than 1, so the bound is vacuous. A bound greater than 1 says only that the soundness error is at most a probability, which is true by definition. In that regime the bound carries no information.

For 80-bit PQ soundness: $(2q + 1)^2 / |C| \le 2^{-80}$, so $|C| \ge (2q + 1)^2 \cdot 2^{80}$. $(2q + 1)^2 = (2^{17} + 1)^2$ is strictly greater than $2^{34}$, so the minimum real bit width is strictly greater than $34 + 80 = 114$, and the smallest integer (or power-of-two) that satisfies the strict inequality is 115. The toy $|C| = 1013$ has $\log_2 |C| \approx 9.985$, so the challenge space must grow by approximately $115 - 9.985 \approx 105$ bits beyond the toy parameters. The integer form $115 - \lceil \log_2 1013 \rceil = 115 - 10$ gives the same 105, which is what the block below computes. What the 115-bit width does not establish is that Schnorr is post-quantum secure at it: the compiled bound is only as good as the assumed quantum interactive error, and Schnorr’s own hardness assumption falls to Shor at any challenge width.

import math
q = 2 ** 16
vacuous_bits = math.log2((2 * q + 1) ** 2 / 1013)
csize_min_bits = math.ceil(math.log2((2 * q + 1) ** 2) + 80)
growth = csize_min_bits - math.ceil(math.log2(1013))
print(round(vacuous_bits, 2), vacuous_bits > 0)
print(csize_min_bits, growth)
# ==> 24.02 True
# ==> 115 105

References

Don, J., Fehr, S., Majenz, C., & Schaffner, C. (2019). Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model. Advances in Cryptology — CRYPTO 2019. https://doi.org/10.1007/978-3-030-26951-7_13