Chapter 33: Fiat-Shamir in the QROM
A deployed post-quantum zero-knowledge system using Fiat-Shamir sits in one of three tiers: three-move sigma protocols (Tier 1), multi-round interactive arguments (Tier 2) and FRI-based SNARKs (Tier 3). Three-move sigma protocols have a published QROM bound (Don, Fehr, Majenz and Schaffner 2019, DFMS19 from here on). Multi-round interactive arguments have one as well, from three of the same authors (Don, Fehr and Majenz 2020, labelled DFMS20 after its predecessor).
FRI and batched FRI that fold by two over a smooth multiplicative subgroup, and Plonk-like SNARKs built on them, have an asymptotic QROM Fiat-Shamir bound (Block et al. 2023). It comes from lifting round-by-round soundness with Chiesa, Manohar and Spooner’s QROM theorem for the Ben-Sasson-Chiesa-Spooner (BCS) transformation. The plain FRI sub-routine also has a classical-ROM concrete-security analysis at deployed and near-deployed parameters (Block-Tiwari 2024). Neither gives a post-quantum soundness number at the deployment parameters of the production pipelines this Part reads, and the QROM accounting that would give one is open (Ch 34 Section 5.6).
L4 is the non-interactivity layer of the four-layer decomposition defined in Ch 31. For systems that compile an interactive protocol to a non-interactive proof via the Fiat-Shamir transform, L4 means the random oracle model is the hash-function idealization under which the compilation is analyzed. Ch 32 built the L2 commitment schemes that L4 compiles. The rest of the chapter presents each tier’s QROM reduction. For the first two it derives a challenge width, the first under DFMS19 and a premise on the protocol’s interactive error, the second under a stipulated model whose widths are not certified minima. For the third, FRI’s, it derives none.
Which transforms survive the quantum oracle
Section titled “Which transforms survive the quantum oracle”The three-tier classification maps to specific published results. For three-move sigma protocols compiled via a single random oracle query, DFMS19 gives a QROM reduction with soundness loss quadratic in the adversary’s quantum query budget (Don et al., 2019). For multi-round interactive arguments compiled via per-round oracle queries, DFMS20 gives a QROM reduction whose loss is polynomial in the query budget only for a fixed number of rounds: the exponent grows with the round count, and the preservation corollary is stated for constant-round protocols (Don et al., 2020, sec. 5.2).
For FRI-based SNARKs, Block et al. 2023 prove an asymptotic Fiat-Shamir security result in the QROM for FRI and batched FRI (Block et al., 2023). They prove FRI’s round-by-round soundness and obtain the QROM result from Chiesa, Manohar and Spooner’s theorem that the BCS transformation of a round-by-round-sound IOP is secure in the QROM (Chiesa et al., 2019). Block-Tiwari 2024 then audit the concrete security of plain FRI, without batching, in the classical ROM at deployed and near-deployed parameter settings (Plonky2, stone-prover, SHARP (StarkWare’s shared prover), dYdX, Miden, RISC Zero, era-boojum) and in the lambdaworks library. They report provable security 21 to 63 bits below conjectured security in all but one of the surveyed sets, the exception being lambdaworks’ provable-target settings (Block & Tiwari, 2024).
A concrete-parameter QROM accounting at a production pipeline this Part reads would compose interactive FRI soundness, Fiat-Shamir loss, Merkle binding, hash-output width, grinding, recursion, and per-system parameter choices, and it is the open item Ch 34 Section 5.6 records.
A Schnorr proof, interactive and compiled
Section titled “A Schnorr proof, interactive and compiled”The Schnorr protocol is the canonical three-move sigma protocol (Schnorr, 1991). The Fiat-Shamir transform (Fiat & Shamir, 1987) applied to it is this chapter’s worked example of QROM Fiat-Shamir analysis. A prover proves knowledge of a witness x in Z_n such that h = g^x mod p, for public g and h in the subgroup of order n that g generates. A zero witness x = 0 is excluded only because it would force the public key h = 1 and trivialize the relation. A verifier therefore rejects h = 1 and checks h^n = 1 mod p before anything else. A key failing either check has no witness, yet a prover can pass every challenge when h = 1, and on the chapter’s toy group 507 of the 1013 when h lies outside the subgroup. The subgroup order is written n throughout Ch 33 to reserve q for the adversary’s quantum query budget in the sections that follow. The toy group reused from the Ch 32 toy_kzg module has p = 2027 = 2 * 1013 + 1, n = 1013, and generator g = 4, which spans the order-n subgroup of F_p^*.
The interactive protocol has three moves. The prover picks a fresh nonce r uniformly in Z_n and sends the commitment a = g^r mod p. The reference implementation also draws r from [1, n - 1], which the protocol definition does not require. The printed blocks below omit that check and the two key checks, which their honestly generated keys pass. The verifier picks a challenge e uniformly in Z_n and sends it. The prover sends the response z = (r + e * x) mod n. On a key that passes both checks, the verifier accepts iff g^z == a * h^e mod p. Completeness follows from g^z = g^{r + e * x} = g^r * (g^x)^e = a * h^e.
The Fiat-Shamir compilation replaces the verifier’s challenge with a hash of the transcript so far. The compiled prover computes a = g^r, then derives e = H(pk || a) for a hash function H modeled as a random oracle, and sends (a, z). The verifier recomputes e = H(pk || a) and runs the same verification equation. No interaction is needed. The random oracle query is local to each party.
The operator decision is whether the deployment needs non-interactivity at the cost of inheriting a QROM reduction loss.
(a, z) and no interaction is required.# Block 1: pedagogical slice of# fiat_shamir_qrom.fiat_shamir.interactive_prove and interactive_verify# (stdlib only).
PRIME, ORDER, G = 2027, 1013, 4 # toy group reused from Ch 32 toy_kzg
def interactive_prove(sk, challenge, nonce): commitment = pow(G, nonce, PRIME) response = (nonce + challenge * sk) % ORDER return commitment, response
def interactive_verify(pk, commitment, challenge, response): lhs = pow(G, response, PRIME) rhs = (commitment * pow(pk, challenge, PRIME)) % PRIME return lhs == rhs
sk = 123pk = pow(G, sk, PRIME)commitment, response = interactive_prove(sk, challenge=456, nonce=789)print(interactive_verify(pk, commitment, 456, response))# ==> TrueEvery Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch33/, one file per block. Appendix C covers the clone and the environment they run on.
Ch 31 opened on this protocol and showed its three properties on the same toy group. They are completeness, special soundness through the extraction in the next paragraph, and perfect special honest-verifier zero knowledge, whose simulated transcripts are distributed exactly as the real ones. All three are statements about a key that passes the two checks above, since a key failing either check has no witness to extract. The third is also a statement about the protocol as defined, with r uniform over Z_n. The reference implementation’s nonce is never 0, so its commitment is never 1, and its transcripts miss the one simulated transcript per challenge that has a = 1. As Ch 31 explains, the zero knowledge shown there covers neither a verifier that computes e from a nor the compiled proof below, whose challenge comes from a fixed hash function.
This is a public-coin three-move protocol: the verifier’s messages are its random coins, here the challenge e. Classical knowledge soundness comes from a rewinding extraction: given two accepting transcripts (a, e_1, z_1) and (a, e_2, z_2) with e_1 != e_2, the witness is x = (z_1 - z_2) * (e_1 - e_2)^{-1} mod n. Rewinding is the classical technique whose oracle-side half the QROM analysis must replace. The classical argument records the adversary’s oracle queries and re-runs it from the decisive one with a different answer. A quantum adversary queries in superposition, and DFMS19’s starting point is that such queries cannot be observed or copied without disturbing them, so the reduction cannot find the decisive query by looking (Don et al., 2019, sec. 1).
Random oracle models, classical and quantum
Section titled “Random oracle models, classical and quantum”The classical random oracle model (ROM) treats a hash function H as an idealized function from {0, 1}^* to its output range. Adversaries access H through classical queries: submit x, receive H(x). On a fresh input the output is drawn uniformly from the range and cached; on a repeat query the cached value is returned. Security proofs in the ROM exploit two properties. The reduction sees every query, so it can program the oracle at specific points to inject challenges. The reduction can rewind the adversary, re-running it from a chosen state against a fresh oracle sample.
The quantum random oracle model (QROM) grants the adversary oracle access via quantum queries. A query on input register |x> and response register |y> is mapped to |x> |y XOR H(x)>. Applied to a superposition sum_x alpha_x |x> |y> it yields sum_x alpha_x |x> |y XOR H(x)> (Boneh et al., 2011). The reduction cannot observe the query without measurement, and measurement collapses the superposition. No-cloning rules out keeping a copy of the adversary’s state, so the classical record-and-replay argument, which saves the state and reruns the adversary from it, has no direct quantum analogue. Rewinding after a measurement is still possible under extra hypotheses, which the DFMS19 discussion below states. Classical ROM proofs that rely on query observation or rewinding therefore do not port directly to the QROM (Don et al., 2019; Zhandry, 2019).
Two technical tools replace the classical toolkit. The measure-and-reprogram technique (DFMS19) measures one of the adversary’s queries, records the input, reprograms the oracle at that input, and continues the reduction from the measured input (Don et al., 2019). The compressed-oracle technique (Zhandry) maintains a compact representation of the adversary’s superposition of queries, so the reduction can record those queries in the oracle’s own register, outside the adversary’s view, without the adversary detecting it (Zhandry, 2019). Early QROM NIZK constructions predate both techniques and use bespoke quantum-aware simulators (Unruh, 2015).
Three tiers of Fiat-Shamir compilation
Section titled “Three tiers of Fiat-Shamir compilation”Three-move sigma with Fiat-Shamir
Section titled “Three-move sigma with Fiat-Shamir”DFMS19 is the baseline QROM result for three-move sigma protocols with Fiat-Shamir compilation. The theorem (informally): let Sigma be a three-move public-coin protocol with challenge space C and soundness error epsilon. Suppose Sigma is sound against a static dishonest prover and its challenge space is superpolynomially large. That is all DFMS19’s soundness statement asks of the protocol. The quantum-facing hypothesis discussed below, quantum computationally unique responses, belongs to the proof-of-knowledge statement rather than to this bound (Don et al., 2019). Let FS[Sigma] be the Fiat-Shamir compilation via a random oracle H with range C. Then for any quantum adversary that makes at most q queries to H, the soundness error of FS[Sigma] in the QROM is bounded by
epsilon_qrom <= (2q + 1)^2 * epsilon.The loss multiplies the interactive soundness error rather than sitting beside it. DFMS19 states the coefficient asymptotically as O(q^2) together with a lower-order additive residue; DFMS20 sharpens the same statement to an exact (2q + 1)^2 with no additive term, and that is the form printed above (Don et al., 2020). For a protocol whose interactive soundness error is at most 1 / |C| against the quantum prover the reduction produces, the bound reads epsilon_qrom <= (2q + 1)^2 / |C|, the form the rest of this chapter sizes parameters against. The measure-and-reprogram section below says why the error must hold against that prover. A protocol with a larger interactive soundness error pays the same factor on the larger number. Schnorr shows the transcripts and the extraction, and its 1 / |C| is a knowledge error, a different notion.
The quadratic shape is the load-bearing asymptotic, and both theorem statements should be read in full before computing margins inside a specific scheme’s security proof. The quadratic term is the measure-and-reprogram reduction loss, internal to a single run of the lemma. The measure-and-reprogram section below derives it. The short version: DFMS19 decomposes the reduction into a hybrid argument that guesses the adversary’s “decisive” query position and replaces the oracle response at that position with a fresh sample. The two factors of (2q + 1) come from the hybrid’s internal combinatorics, not from two separate runs of the adversary. The interactive soundness error the factor multiplies is established separately, for the protocol against quantum provers, and does not re-multiply the factor.
The “quantum computationally unique responses” condition is not the QROM analog of the classical special-soundness property that supports rewinding extraction, and it is not a hypothesis of the soundness bound above. DFMS19 uses it for the proof-of-knowledge statement, paired with a separate hypothesis, t-soundness: from any first message a and any t accepting responses to t independently uniform challenges, a witness can be computed efficiently, except with negligible probability over the challenges. t-soundness is the hypothesis that quantifies over several challenges. Unique responses quantifies over none: it fixes the commitment and the challenge and constrains the responses to that one pair.
Formally the verification predicate V(x, ., ., .), read as a relation between commitment-challenge pairs and responses, must be collapsing from the response space to the commitment-challenge space. For a fixed first message and challenge, no quantum adversary can tell whether a superposition over accepting responses was measured. That is strictly stronger than the classical requirement that two accepting responses for the same first message and challenge be hard to find. The strengthening is load-bearing rather than cosmetic: the classical computational version is known not to suffice (Don et al., 2019, sec. 5). The condition must be justified from the underlying algebraic assumption in each concrete scheme, not assumed generically.
For Schnorr over a prime-order group with canonical responses in Z_n, unique responses for a fixed commitment and challenge hold algebraically. If two responses z_1 and z_2 both verify against the same (a, e), then g^{z_1} = g^{z_2}, and in a prime-order group this forces z_1 = z_2 mod n. Exactly one accepting response exists per pair, so there is no superposition to distinguish and the relation is collapsing outright. Schnorr discharges the condition with no computational assumption behind it. Knowledge soundness needs no assumption either: two accepting transcripts with distinct challenges give the witness, as the extraction above shows. What rests on discrete logarithm hardness is the identification scheme’s security: classically, rewinding a successful impersonator gives two such transcripts, and so the discrete logarithm of h.
For lattice-based sigma protocols the situation is scheme-specific. Fiat-Shamir-with-aborts signatures such as ML-DSA (the pre-standard construction was Dilithium) do not fit the plain DFMS19 framework. The QROM treatment FIPS 204 cites for ML-DSA’s assumptions (National Institute of Standards and Technology, 2024, sec. 3.2) is Kiltz, Lyubashevsky and Schaffner’s. It handles the abort branch, and it gives a tight reduction from Module-LWE for a modified Dilithium-QROM variant whose identification scheme admits lossy keys. For Dilithium’s own parameters, whose identification scheme has no lossy mode, it keeps the Module-LWE assumption and replaces the lossy-key step with a second assumption, SelfTargetMSIS. The deterministic scheme is then UF-CMA secure in the QROM under Module-LWE and SelfTargetMSIS together (Kiltz et al., 2018, sec. 1.1).
Barbosa et al. and Devevey et al. later found errors in Kiltz, Lyubashevsky and Schaffner’s analysis and gave corrected proofs (Barbosa et al., 2023; Devevey et al., 2023). Among the errors is a gap, which Kiltz, Lyubashevsky and Schaffner confirmed, in the analysis’s step from security against an attacker who sees no signatures to security against chosen-message attacks (Barbosa et al., 2023). Barbosa et al. show that Dilithium’s claimed security level still holds once the gap is closed (Barbosa et al., 2023). DFMS19 treats the underlying lattice protocol by a different route, as a proof of knowledge under a collapsingness assumption on the SIS function and with no lossy keys (Don et al., 2019, sec. 6.2).
# Block 2: pedagogical slice of fiat_shamir_qrom.fiat_shamir.fs_prove# and fs_verify (stdlib only).
import hashlib
PRIME, ORDER, G = 2027, 1013, 4 # toy group reused from Ch 32 toy_kzg
class LazyOracle: def __init__(self, seed=b""): self.seed = seed self.cache = {}
def query(self, x): if x in self.cache: return self.cache[x] digest = hashlib.sha256(self.seed + x).digest() value = int.from_bytes(digest, "big") % ORDER self.cache[x] = value return value
def transcript_bytes(pk, commitment): return pk.to_bytes(4, "big") + commitment.to_bytes(4, "big")
def fs_prove(sk, pk, nonce, oracle): commitment = pow(G, nonce, PRIME) challenge = oracle.query(transcript_bytes(pk, commitment)) response = (nonce + challenge * sk) % ORDER return commitment, response
def fs_verify(pk, commitment, response, oracle): challenge = oracle.query(transcript_bytes(pk, commitment)) lhs = pow(G, response, PRIME) rhs = (commitment * pow(pk, challenge, PRIME)) % PRIME return lhs == rhs
sk = 42pk = pow(G, sk, PRIME)oracle = LazyOracle(seed=b"ch33-demo")commitment, response = fs_prove(sk, pk, nonce=200, oracle=oracle)print(fs_verify(pk, commitment, response, oracle))# ==> TrueThe block demonstrates two properties of the compilation. The challenge is a deterministic function of the transcript: a second verifier with the same oracle recomputes the same challenge and the same verification equation. The proof consists only of (commitment, response). The challenge is reconstructed from the transcript via a single oracle query.
Two caveats keep the block honest as a demo and not as a deployment template. LazyOracle.query reduces a SHA-256 digest modulo ORDER, which is biased for any ORDER that does not divide 2^256; here the bias is at most 1013 / 2^256, about 2^-246, and irrelevant. What production challenge sampling adds is a stated bound: either hash at least log_2 |C| + 128 bits before reducing, so the bias is provably below the security target, or use rejection sampling, which is exactly uniform. transcript_bytes concatenates two fixed-width 4-byte encodings, which is unambiguous only because the toy p = 2027 fits in four bytes. Production Fiat-Shamir transcripts must be domain-separated by purpose tag and length-delimited so that no two distinct prover-message tuples can produce the same byte sequence.
Multi-round Fiat-Shamir
Section titled “Multi-round Fiat-Shamir”Multi-round interactive arguments compile via per-round Fiat-Shamir queries. The prover sends message m_1, derives e_1 = H(pk || m_1), sends m_2, derives e_2 = H(pk || m_1 || e_1 || m_2), and so on for r rounds. Throughout this section r counts the number of Fiat-Shamir verifier-challenge rounds, not the total number of prover-or-verifier messages. Each prover message is appended to the transcript prefix that feeds the next oracle query. The final proof is the full transcript of prover messages. The verifier recomputes every challenge by replaying the transcript into the oracle.
The DFMS20 result extends the DFMS19 analysis to arbitrary-round protocols (Don et al., 2020). Its Corollary 13, for a public-coin protocol with r challenge rounds and challenge set C, turns a Fiat-Shamir adversary making q queries into an interactive prover whose success probability is at least r! / (2q + r + 1)^{2r} times the adversary’s, minus an additive term that sums to r! / |C| over all statements. Read as a bound on the compiled protocol, that is
Pr[A breaks FS-compiled protocol] <= ((2q + r + 1)^{2r} / r!) * Pr[A breaks interactive protocol] + (2q + r + 1)^{2r} / |C|.This chapter sizes parameters with a stipulated algebraic model rather than with that corollary. The model keeps the multiplicative shape, rounds the coefficient to (2q + 1)^{2r}, and drops the additive term:
Pr[A breaks FS-compiled protocol] <= (2q + 1)^{2r} * Pr[A breaks interactive protocol].The model is not a conservative reading of the corollary, and the widths it produces are not theorem-backed sufficient conditions. The dropped term decides that: at q = 2^80 and r = 12 it is about 2^1771 for a challenge set of 2^173 elements, so the corollary as stated certifies nothing at the widths this section computes. DFMS20’s Remark 14 says so for sequential repetition, where the interactive error is 1 / |C|^r: “the term proportional to 1/|C| renders the bound from the above theorem trivial”. The same remark names the repair, enlarging each challenge with bits the protocol ignores so that |C| in the additive term grows while the protocol’s own soundness does not change. A deployment that wants the theorem rather than the model applies that padding and instantiates Corollary 13 with the protocol’s actual interactive error, which for a FRI-based protocol is not 1 / |C|^r (see the subsection on DFMS20’s hypotheses below). What the model keeps is the polynomial-in-q, exponent-linear-in-r shape, which is the load-bearing fact for how a width scales with q and r, and that shape is not an artifact of the proof technique that a sharper analysis could remove. The same paper exhibits a Grover-search attack showing the DFMS19 quadratic loss optimal up to a small constant factor, and the multi-round bound tight up to a factor depending only on the round count (Don et al., 2020).
The factor (2q + 1)^{2r} generalizes the three-move (2q + 1)^2 to r rounds: each round adds one pair of index-guesses in the lemma’s internal hybrid, so the exponent grows linearly with the round count. For a per-round soundness error eps_round = 1 / |C| that compounds independently across rounds, as in the sequential repetition of a sigma protocol, the interactive soundness error is 1 / |C|^r, and the model’s compiled bound becomes (2q + 1)^{2r} / |C|^r. Under the model, a deployment with many rounds sizes |C| so that |C|^r outruns the (2q + 1)^{2r} growth. Both halves of that sentence are the model’s: 1 / |C|^r is an assumption of the repeated-protocol example and not a property of any protocol with r challenges, and the rule inherits the dropped additive term.
Block 3 demonstrates the classical scaffolding of the DFMS20 reduction: pick one of the adversary’s queries to measure, record the input, reprogram the oracle at that input to a fresh value, and re-run the adversary. The second run’s response at the measured input equals the reprogrammed value by construction. The full quantum reduction is not equivalent to two classical runs with a cached query log. It uses the reprogramming property inside a single-shot quantum simulator that selects a random branch and a measurement position before the adversary’s first query. The post-measurement quantum state cannot be cloned to support a literal “rerun”. The classical block illustrates the algebraic invariant that the quantum proof builds on, not the proof itself.
# Block 3: pedagogical slice of the reference implementation's# measure_and_reprogram.simulate_classical_extraction (stdlib only).
import hashlib
class LazyOracle: def __init__(self, modulus, seed=b""): self.modulus = modulus self.seed = seed self.cache = {} self.programmed = {} self.log = []
def query(self, x): self.log.append(x) if x in self.cache: return self.cache[x] if x in self.programmed: value = self.programmed[x] else: digest = hashlib.sha256(self.seed + x).digest() value = int.from_bytes(digest, "big") % self.modulus self.cache[x] = value return value
def reprogram(self, x, value): if x in self.cache: raise ValueError("cannot reprogram a queried point") if value < 0 or value >= self.modulus: raise ValueError("value outside oracle range") self.programmed[x] = value
def adversary(oracle): return tuple(oracle.query(t) for t in (b"q0", b"q1", b"q2"))
MODULUS, SEED = 1013, b"mr-demo"first_oracle = LazyOracle(MODULUS, SEED)first_output = adversary(first_oracle)
measured_index = 1measured_input = first_oracle.log[measured_index]second_oracle = LazyOracle(MODULUS, SEED)second_oracle.reprogram(measured_input, 777)second_output = adversary(second_oracle)
print(second_output[measured_index] == 777)# ==> TrueThe block’s invariant is that the second run’s response at the measured index equals the reprogrammed value. The adversary in this block issues a fixed, non-adaptive query schedule, so the first and second runs share the same query sequence. Only the response at the measured input changes. The code block demonstrates the reprogramming mechanic in a classical setting. The quantum reduction does not argue that the reprogrammed oracle is indistinguishable from a fresh one. It relates success probabilities, as the measure-and-reprogram section below states.
FRI-based SNARK Fiat-Shamir
Section titled “FRI-based SNARK Fiat-Shamir”FRI-based SNARKs compose a multi-round Fiat-Shamir compilation with a Merkle commitment at each round and a proximity-gap argument over a Reed-Solomon code (Ben-Sasson et al., 2018, 2020). The L2 constructions are those Ch 32 derived. The L4 compilation adds per-round Fiat-Shamir challenges that fold the prover’s committed codeword. The generic DFMS20 multi-round bound is the wrong instrument to apply directly here. FRI’s Fiat-Shamir compilation has a dedicated QROM analysis that exploits the protocol’s structure: it proves FRI’s round-by-round soundness and lifts it into the QROM with Chiesa, Manohar and Spooner’s theorem (Block et al., 2023; Chiesa et al., 2019). So the right reduction loss is the FRI-specific bound, not the protocol-agnostic (2q + 1)^{2r} form.
Block, Garreta, Katz, Thaler, Tiwari, and Zajac (ASIACRYPT 2023) is a dedicated Fiat-Shamir security analysis for FRI and related SNARKs (Block et al., 2023). The paper proves that FRI, when made non-interactive via Fiat-Shamir, is secure in the quantum random oracle model. The paper proves FRI’s round-by-round soundness and takes the QROM result from Chiesa, Manohar and Spooner’s theorem that the BCS transformation of a round-by-round-sound IOP is secure in the QROM (Chiesa et al., 2019). It cites that theorem rather than reproving it (Theorem 3.15 in Block et al., 2023). Asymptotic Fiat-Shamir soundness bounds against O(q)-query quantum adversaries are stated for FRI and batched FRI. The analysis proves the result for Plonk-like protocols such as Plonky2 and sketches it for ethSTARK and RISC Zero, all of them protocols that invoke FRI inside their compilation pipeline.
Block and Tiwari (SCN 2024) carry that asymptotic analysis into a concrete-parameter regime in the classical ROM (Block & Tiwari, 2024). They audit deployed and near-deployed parameter settings (Plonky2, stone-prover, SHARP, dYdX, Miden, RISC Zero, era-boojum) and the lambdaworks library. They report that provable non-interactive FRI security lags conjectured security by 21 to 63 bits in all but one of the surveyed sets, the exception being lambdaworks’ provable-target settings. Their parameter guidelines for roughly 100-bit provable security are computed without grinding, take the field size, message length and rate as inputs and derive the query count, and find no feasible setting over a 128-bit field (Block & Tiwari, 2024, sec. 4.3). The Block-Tiwari analysis is in the classical ROM, not the QROM.
The closest 2025 follow-on is Chiesa and Orrù’s duplex-sponge Fiat-Shamir construction (Chiesa & Orrù, 2025). It gives concrete knowledge-soundness and zero-knowledge bounds, generic rather than at any deployment’s parameters, for the deployed sponge-based Fiat-Shamir pattern, the transcript construction used when production STARK pipelines absorb prover messages and squeeze challenges through a sponge primitive. The compiled argument’s zero-knowledge error is driven by the honest-verifier zero-knowledge error of the interactive proof underneath. The same paper reports that indifferentiability, which is proven for the duplex sponge and for many other modes, is insufficient on its own to establish either property for a non-interactive argument.
That analysis sits in the classical ideal permutation model, not the QROM, and its authors list security against superposition queries to the permutation as an open question (Chiesa & Orrù, 2025). A 2026 preprint proves the construction’s adaptive zero-knowledge against quantum attackers with access to the permutation in both directions, assuming a sub-exponentially secure quantum pseudorandom permutation only when the attacker’s advice depends on the permutation (Theorem 11 in Huang et al., 2026). It proves soundness for three-round protocols only (Theorem 19 in Huang et al., 2026). The authors write that the proof “can be extended to multi-round protocols at the cost of additional reprogrammings”, but they state no such theorem or bound (§G.1 in Huang et al., 2026). A many-round compilation such as FRI’s is therefore not among its theorems, and a literature search of the record as it stood on 19 October 2026 found no later paper proving many-round soundness for the duplex-sponge transform against quantum attackers.
The ethSTARK documentation specifies settings for 80, 100 and 128 bits of security, priced in the random-oracle model with the grinding bits counted, where at a fixed rate and grinding budget the query count and the extension degree are what move between the three targets (Ben-Sasson, 2021, sec. 5.10).
The measure-and-reprogram technique
Section titled “The measure-and-reprogram technique”The measure-and-reprogram lemma is the core QROM reduction underlying this chapter’s DFMS19 and DFMS20 bounds. The DFMS19 statement (restated informally for this chapter): let A be a quantum algorithm making at most q queries to a random oracle H: X -> Y. Let V be a binary predicate on pairs (x, y) in X * Y. DFMS19 Theorem 2 bounds the probability that A outputs a pair (x, H(x)) satisfying V by a multiple of the probability that a measure-and-reprogram sampler produces (x_star, y_star) satisfying V.
The simulator of DFMS20’s Theorem 2 runs A and measures one of its q + 1 queries, the final output counted as a query. It picks each actual query with probability 2 / (2q + 1) and the final output with probability 1 / (2q + 1), which is a uniform choice among 2q + 1 position-and-branch pairs. The measured input is x_star. The second stage receives a fresh uniform Theta in Y, answers the measured query either with the original oracle or with the oracle reprogrammed at x_star to Theta according to the branch, answers every later query with the reprogrammed oracle, and outputs whatever A outputs, a possibly quantum z. The bound, for any predicate V, is
Pr[V(x, H(x), z)] <= (2q + 1)^2 * Pr[V(x_star, Theta, z)].The reduction loss is (2q + 1)^2 for a three-move protocol. DFMS19 proves the bound with an asymptotic O(q^2) coefficient and a negligible additive residue; DFMS20 removes the residue and pins the coefficient exactly, which is the form printed above (Don et al., 2020). When Pr[V(x_star, Theta, z)], the success probability of an interactive prover that is itself quantum, is bounded by an interactive soundness error 1 / |C| established against such provers, the factor multiplies it, giving the (2q + 1)^2 / |C| bound stated for the three-move sigma tier above.
The operator decision is which of the three tiers (three-move, multi-round, FRI-based) describes the candidate deployment and therefore which published bound applies.
q + 1 query positions with a branch, reprograms the oracle at the measured input to a fresh Theta, and continues the adversary. Its first stage yields the classical x* and its second stage returns whatever the adversary returns, a possibly quantum z, which the predicate is then evaluated on against Theta. The (2q + 1)^2 factor relates the two success probabilities rather than describing a classical pair.The (2q + 1)^2 factor is internal to a single run of the lemma. The DFMS19 proof decomposes the reduction into a hybrid argument. The hybrid guesses the adversary’s “decisive” query position and replaces the oracle response at that position with a fresh sample. The two factors of (2q + 1) come from the hybrid’s internal combinatorics, not from two separate runs of A.
Reprogramming the oracle at the measured point is not something the adversary is unable to notice: an adversary that queried that point classically before the reprogramming and again after it sees the change with probability 1 - 1/|Y|, and classical queries are allowed in the QROM. The measure-and-reprogram result is not an indistinguishability claim. It relates the simulator’s success probability to the adversary’s: DFMS19’s Lemma 1 and Theorem 2 carry a 1 / O(q^2) coefficient and an additive residue bounded by 1 / (2q|Y|) when summed over all x_0, and DFMS20’s Theorem 2 removes the residue, which is the (2q + 1)^2 form printed above (Don et al., 2019, 2020). Boneh et al.’s Lemma 3 is a different statement, about replacing the whole oracle by one whose every output is drawn from a distribution epsilon-close to uniform, at a cost of 4 q^2 sqrt(epsilon) in the adversary’s output distribution (Boneh et al., 2011). The q + 1 indices enumerate the adversary’s q oracle queries together with one extra slot for its final output. The factor of 2 in 2q + 1 comes from the two-option selector at each of the q query positions. The output slot has one option, so the pairs number 2q + 1 and not 2(q + 1).
The DFMS19 simulator is not literally “measure the chosen query, reprogram, continue from there”. Instead, it selects the position and a binary branch before the adversary’s first query. It then measures the input register of the i_star-th query, samples a fresh y_star, and uses the selector to decide how the measured query is answered before continuing the adversary against the reprogrammed oracle. The selector is what keeps the measured branch’s success probability related to the adversary’s rather than letting the measurement destroy the reduction, and DFMS20’s uniform choice over 2q + 1 position-and-branch pairs is what removes DFMS19’s additive residue.
A separate step applies the lemma to Fiat-Shamir Sigma protocols. The right-hand side is the success probability of an interactive prover, and that prover is quantum: it is the simulator with A inside it. So the 1 / |C| that turns the bound into (2q + 1)^2 / |C| has to be the sigma protocol’s soundness error against quantum dishonest provers, established for the protocol itself. Computational special soundness does not supply it. DFMS19 says of a sigma protocol that is computationally special sound but not computationally sound that “in the quantum setting, special soundness does not imply ordinary soundness” (Don et al., 2019). That is why the three-move bound is (2q + 1)^2 / |C| and not (2q + 1)^4 / |C|: the theorem is applied once, and the interactive error it multiplies is a separate, independently established quantity.
Perfect special soundness does supply the 1 / |C|, against any prover, quantum included. For a false statement and a fixed first message, two challenges with accepting responses would give a witness the statement does not have. So at most one challenge can be answered, and a uniform challenge is that one with probability at most 1 / |C|. That is a bound on accepting false statements, which is how DFMS19 defines soundness (Definition 9 in Don et al., 2019). Every key that passes Schnorr’s two checks has a witness, so what Schnorr identification and its signatures need is knowledge extraction, which DFMS19 defines separately as a proof of knowledge (Definition 14 in Don et al., 2019). DFMS19’s signature result asks for “a proof-of-knowledge against quantum dishonest provers” (Don et al., 2019).
The compressed-oracle technique is the contrasting approach. Instead of measuring a query, the reduction maintains a compact representation of the oracle as a map from queried inputs to the adversary’s current superposition of responses (Zhandry, 2019). That register is a purification of the adversary’s state, so measuring it after the adversary has finished is undetectable, and Zhandry’s Lemma 5 relates what the adversary knows about an oracle output to what the measured database holds. A simulator that has to test the database during the run does disturb it, and Zhandry’s contribution is to show the disturbance is small. Compressed oracles appear in specialized arguments such as QROM indifferentiability proofs and Fujisaki-Okamoto proofs. The published QROM Fiat-Shamir bounds in this chapter (DFMS19, DFMS20) use measure-and-reprogram, and DFMS20 shows by a Grover-search attack that their quadratic loss is optimal up to a small constant factor (Don et al., 2020).
The classical rewinding extraction the Schnorr section described does not survive the transition to QROM. Rewinding requires running the adversary from an intermediate state against a different oracle while observing the adversary’s queries. The measurement required to observe those queries collapses the superposition, which destroys the state the reduction would rewind to. Measure-and-reprogram replaces the oracle-side half of that argument: one query is measured inside a hybrid argument and the oracle is reprogrammed at the measured input, which turns the Fiat-Shamir prover into an interactive prover for the sigma protocol. Extraction is then the sigma protocol’s own job, and DFMS19’s extractor for it still rewinds. Theorem 25 measures the response and rewinds the adversary on the measured state, and quantum computationally unique responses is what makes that measurement computationally indistinguishable from one that leaves an accepting state undisturbed (Don et al., 2019, sec. 5).
Cost of the quantum oracle
Section titled “Cost of the quantum oracle”For the first two tiers, the QROM reduction loss translates into a challenge-width requirement, in the second through the chapter’s model. Setting (2q + 1)^2 / |C| <= 2^{-k} and taking logs gives c_bits >= 2 log_2(2q + 1) + k. For 2q >> 1, log_2(2q + 1) is strictly greater than q_bits + 1 (with the gap a vanishingly small log_2(1 + 2^{-(q_bits+1)})), so the exact lower bound is just barely greater than 2 q_bits + 2 + k. Approximating 2q + 1 by q, which drops the doubling as well as the +1, gives the commonly quoted three-move sigma minimum of c_bits >= 2 q_bits + k, an under-estimate by 3 integer bits compared with the minimum power-of-two challenge space.
For multi-round protocols the model of the multi-round section gives (2q + 1)^{2r} / |C|^r <= 2^{-k}. This rearranges to c_bits >= 2 log_2(2q + 1) + k / r per round, approximately 2 q_bits + 2 + k / r, with the ceiling taken once at the end on the per-round width rather than on k / r. Adding rounds amortizes the target soundness term across the rounds, so the per-round challenge width approaches 2 (q_bits + 1) from above as r grows. The aggregate challenge budget across the r rounds is r * c_bits >= 2 r (q_bits + 1) + k, which scales linearly in r.
Table 33.1. Minimum challenge width at q = 2^{80} against a k = 128 bit PQ soundness target.
| Tier | Lower bound on c_bits | Minimum integer width | Commonly quoted approximation |
|---|---|---|---|
Tier 1: three-move sigma (DFMS20’s (2q + 1)^2, interactive error 1 / card(C) against quantum provers) | 2 log_2(2q + 1) + k, just above 290.0 | 291 bits | 2 q_bits + k = 288, short by 3 |
Tier 2: multi-round FS, r = 12 (the chapter’s DFMS20-shaped model) | 2 log_2(2q + 1) + k / r ≈ 172.67 | 173 bits per round | 2 q_bits + ⌈k / r⌉ = 171, short by 2 |
| Tier 3: FRI / BCS SNARK | dedicated FRI bound, not this formula | not derived here | generic DFMS20 model does not apply |
The first expression sits just above an integer, and the strict inequality is what forces the round up: 290.0 plus a vanishingly small positive term rules out 290. The second, 172.67, rounds up to 173 on any reading. The FRI row derives no width because that tier is sized under the dedicated FRI Fiat-Shamir bound rather than the generic DFMS20 formula. Table 33.2 below adds the FS-free Groth16 row, which has no QROM reduction loss and a different migration path. Sapling’s Spend and Output circuits sit in that row as the deployed instance that Ch 31 and Ch 32 flagged. Bounds greater than 1 are vacuous because a probability is at most 1. The parameter-sizing exercise is in finding the smallest |C| at which the bound drops below the target 2^{-k}.
Table 33.2. Fiat-Shamir tiers and QROM-security posture.
| Protocol structure | Relevant technique | Published loss shape | Representative systems |
|---|---|---|---|
| Tier 1: three-move sigma with FS | Measure-and-reprogram (DFMS19; the residue-free (2q + 1)^2 coefficient is DFMS20’s Theorem 2) | (2q + 1)^2 * epsilon, multiplicative with no additive term | Schnorr |
| Tier 2: multi-round FS (r rounds) | Measure-and-reprogram 2.0 (DFMS20) | Corollary 13: ((2q + r + 1)^{2r} / r!) * epsilon + (2q + r + 1)^{2r} / card(C); the chapter’s model keeps (2q + 1)^{2r} * epsilon and drops the additive term | PLONK, Halo 2, Plonky2 (non-FRI subcomponents) |
| Tier 3: FRI / BCS-based SNARK | Dedicated FRI Fiat-Shamir analysis (Block et al. 2023, ASIACRYPT 2023); Chiesa-Manohar-Spooner lift gives QROM bound, for FRI that folds by two, against O(q)-query quantum adversaries; concrete-parameter audit in classical ROM (Block-Tiwari 2024, SCN 2024) | Classical NI/ROM: eps_fs = q * eps_rbr + O(q^2 / 2^kappa). Against O(q)-query quantum adversaries (QROM): Theta(q * eps_fs), hence roughly Theta(q^2 * eps_rbr + q^3 / 2^kappa). FRI-specific, not the generic DFMS20 form. | Plonky2, stone-prover, SHARP, dYdX, Miden, lambdaworks, RISC Zero, era-boojum |
| NIZK via pairing CRS (no FS at L4) | Not applicable (no QROM surface: L4 is the CRS rather than a transform, and its trapdoor falls to the same Shor computation as the L2 pairing) | No QROM loss at L4; the L2 and CRS break is structural, not parameter-bumpable | Groth16 and deployments built on it, including Sapling |
Table 33.2’s FRI row uses the chapter’s q and introduces kappa. q is the quantum query budget against the random oracle, kappa is the random-oracle output length in bits, and eps_rbr is the round-by-round soundness error of interactive FRI. The Block et al. 2023 paper writes the same quantities with capital Q; the table uses lowercase q for consistency with the chapter’s notation elsewhere. The last row’s CRS is the common reference string, the public setup artifact a pairing-based NIZK shares between prover and verifier in place of a Fiat-Shamir oracle. The multi-round FS row classifies only the Fiat-Shamir transcript shape. The post-quantum status of a concrete PLONK, Halo 2, or Plonky2 deployment also depends on the polynomial commitment layer (KZG is broken by Shor at L2; IPA is discrete-log-based; FRI sits in the FRI / BCS row).
The FRI row carries a published QROM Fiat-Shamir bound for FRI that folds by two over a smooth multiplicative subgroup (Block et al. 2023) and a classical-ROM analysis of the plain FRI sub-routine at deployed and near-deployed parameters (Block-Tiwari 2024). A concrete deployment-parameter QROM audit at the parameters of any production FRI pipeline this Part reads requires composing the FRI Fiat-Shamir bound with Merkle binding, hash-output width, grinding bits, recursion, and per-system parameter choices. That composed analysis is system-specific and open, as Ch 34 Section 5.6 records.
The operator decision is to place the candidate deployment in one of Table 33.2’s three Fiat-Shamir rows. In the first, the challenge space or the repetition count can be sized against the reduction loss at the target PQ bit margin, under the premise that the interactive error is 1 / |C|. In the second, the chapter’s model gives only a teaching width, and a certified one comes from Corollary 13 itself, padded and instantiated with the protocol’s actual interactive error. The FRI row gives no width to size against, and only an analysis at the deployment’s own parameters can say whether any change is needed.
(2q + 1)^2 on the interactive error, giving (2q + 1)^2 / |C| only if that error is 1 / |C| against quantum provers. Row 2 is the chapter's model of DFMS20's Corollary 13, coefficient rounded, additive term dropped, and certifies no width. Row 3 is Block et al. 2023's asymptotic QROM bound with Block-Tiwari 2024's classical-ROM analysis of plain FRI (Block et al., 2023; Block & Tiwari, 2024), and its QROM accounting at the deployment parameters of the production FRI pipelines this Part reads is open (Ch 34 Section 5.6). All three rows are amber on Figure 31.2's scale, where amber means a parameter bump or a pending concrete-parameter accounting. The colors grade the Fiat-Shamir step alone: Schnorr's group still falls to Shor (Ch 35, Table 35.2). Block et al.'s QROM bound is proved for FRI that folds by two over a smooth multiplicative subgroup. It reaches Starknet's Stone root only through the extension to larger folds and an interaction trace that Ch 34 Section 5.6 records as unstated, and the Stwo leaves' circle FRI lies outside it.Hypotheses behind DFMS20 and why FRI uses a dedicated bound
Section titled “Hypotheses behind DFMS20 and why FRI uses a dedicated bound”DFMS20’s Corollary 13 applies to any public-coin interactive proof compiled with the multi-round Fiat-Shamir transform of its Definition 11, where challenge i is the hash of the round index, the previous challenge and the current prover message. It has no hypothesis about extractors. What it delivers is a quantum dishonest prover for the interactive protocol, so the interactive protocol has to be secure against that quantum prover, and its Corollary 15 says that for a constant number of rounds soundness and the quantum proof-of-knowledge property carry over to the compiled protocol (Don et al., 2020). Round-by-round soundness and its Chiesa-Manohar-Spooner lift into the QROM belong to the separate analysis of FRI below, not to DFMS20. Schnorr and PLONK-style multi-round protocols are public-coin, which is why DFMS19 and DFMS20 apply to them off the shelf, subject to the additive term the multi-round section records.
FRI-based SNARKs sit apart from the generic DFMS20 application for a more specific reason than “missing literature”. The protocol has a dedicated Fiat-Shamir analysis that proves FRI’s round-by-round soundness and lifts it into the QROM with Chiesa, Manohar and Spooner’s theorem (Block et al., 2023; Chiesa et al., 2019). The right reduction loss is therefore the FRI-specific bound, not the protocol-agnostic (2q + 1)^{2r} form, and applying DFMS20 directly would overshoot the published QROM loss by additional powers of q.
Two distinct loss shapes are stated in Block et al. 2023. Against classical adversaries in the non-interactive ROM, the soundness error is eps_fs = q * eps_rbr + O(q^2 / 2^kappa) for query bound q, random-oracle output length kappa, and round-by-round soundness eps_rbr of interactive FRI. Against O(q)-query quantum adversaries (the QROM result), the transformed argument has adaptive soundness and knowledge error Theta(q * eps_fs), which expands to roughly Theta(q^2 * eps_rbr + q^3 / 2^kappa). The quantum-adversary expression is one factor of q heavier than the classical NI/ROM expression, and Table 33.2’s FRI row carries both.
Sizing a real deployment from either shape still needs the composition the aside above flags as pending: Merkle binding, hash-output width, grinding bits, recursion depth, and per-system parameter choices. Block-Tiwari 2024 performs the plain-FRI part of that composition in the classical ROM, with query-round grinding counted and with batching and larger folds deliberately left out (Block & Tiwari, 2024, sec. 3.3). It reports 21 to 63 bit gaps between provable and conjectured security in all but one of the surveyed configurations, and says its “analysis indicates the security level only for the FRI sub-routine” (Block & Tiwari, 2024). Ch 34 and Ch 35 label every FRI-based concrete number accordingly.
Operator decision at L4
Section titled “Operator decision at L4”The operator decision at L4: place the deployment in the table and read off the reduction loss. In the first tier, size the challenge space against that loss under DFMS19 and the separate premise that the interactive error is 1 / |C|. In the second, the chapter’s model sizes the challenge space and round count only as a teaching exercise, and a deployment that wants a certified width instantiates Corollary 13 with its own interactive error and Remark 14’s padding. In the FRI tier the table gives no loss at deployment parameters, and the last two paragraphs of this section say why and what stands in its place.
For Groth16 and other pairing-based NIZKs the QROM loss is zero because L4 is the CRS rather than a transform, and the CRS trapdoor and the L2 pairing fall to the same Shor computation (Ch 31, Ch 35). Shor’s algorithm breaks that assumption at the curve level by recovering discrete logarithms in the pairing-friendly group. The derivation is in the “KZG: trapdoor in the structured reference string” section of Ch 32. The migration path for Groth16 and its derivatives is not a QROM parameter bump; it is an L2 replacement.
Fiat-Shamir-with-aborts signatures such as ML-DSA sit in Tier 1, but their QROM reduction is not DFMS19’s: it is the Kiltz-Lyubashevsky-Schaffner treatment, which handles the abort branch and, at the standardized parameters, rests on Module-LWE together with SelfTargetMSIS, the second assumption standing in for the lossy key mode those parameters do not have (Kiltz et al., 2018), the assumption FIPS 204 states for ML-DSA (National Institute of Standards and Technology, 2024, sec. 3.2). The three-move sigma subsection above records the 2023 corrections to that treatment. DFMS19 reaches the underlying lattice protocol by another route, under a collapsingness assumption and without lossy keys (Don et al., 2019, sec. 6.2).
Deployed L2 rollups inherit this chapter’s tier placements at the Fiat-Shamir layer. Plonky2-based and STARK-based rollups sit in the FRI row and inherit its deployment-parameter-QROM-accounting-pending status. A Halo2-based rollup’s Fiat-Shamir transcript is covered by DFMS20’s Corollary 13, subject to its additive term. The rollup’s post-quantum posture is dominated by the commitment layer instead: KZG falls to Shor and IPA is discrete-log-based, as Table 33.2’s note records, and no QROM accounting repairs that break.
Asymptotic QROM Fiat-Shamir security for FRI that folds by two over a smooth multiplicative subgroup is published (Block et al. 2023). A classical-ROM analysis of the plain FRI sub-routine at deployed and near-deployed parameters is published (Block-Tiwari 2024) and reports 21 to 63 bit gaps below conjectured security in all but one of the surveyed configurations. No deployment-parameter QROM accounting of the production FRI pipelines this Part reads is among those results, and Ch 34 Section 5.6 records the search for one (Block et al., 2023; Block & Tiwari, 2024).
The operator response is not a parameter bump while that accounting is missing. It is the governance-multisig upgrade path that any of these rollups already carries for unrelated reasons. Block-Tiwari 2024 already supplies classical-ROM parameter guidelines for roughly 100-bit provable security, computed without grinding (Block & Tiwari, 2024, sec. 4.3), and they size no post-quantum change. A QROM accounting at a rollup’s own deployment parameters, if one is published, could certify those parameters, call for a parameter or scheme change, or leave the question open. Whatever change follows ships through the rollup’s upgrade governance. The operational mechanics live in Ch 40; the governance and upgrade-activation machinery is in Ch 41.
Where Chapter 33 ends and Chapter 34 picks up
Section titled “Where Chapter 33 ends and Chapter 34 picks up”This chapter sorted Fiat-Shamir compilations into three tiers and stated each one’s QROM loss. Two of the three close. DFMS19’s theorem multiplies a three-move sigma protocol’s interactive soundness error by (2q + 1)^2, with the residue-free coefficient DFMS20 supplies. Reading that product as (2q + 1)^2 / |C| takes a second premise the theorem does not supply: that the protocol’s interactive soundness error is 1 / |C| against quantum dishonest provers, which computational special soundness does not establish.
An r-round argument is priced by this chapter’s stipulated model at (2q + 1)^{2r} times its interactive error, which is DFMS20’s Corollary 13 with its coefficient rounded and its additive challenge-space term dropped. Table 33.1 turns the theorem and the model into a minimum challenge width at a stated query budget. Only the first of those widths rests on a certified reduction, and it does so only under that 1 / |C| premise. The third tier does not close. A FRI-based SNARK whose FRI folds by two over a smooth multiplicative subgroup is sized under a dedicated bound rather than the generic DFMS20 form. The composition that would turn that bound into a deployment number is the accounting the aside above records as pending.
Chapter 34 takes that third tier and builds it end to end. It assembles the four stages a STARK composes (AIR arithmetization, low-degree extension, FRI proximity testing, and the Fiat-Shamir compilation analyzed here) into one pipeline over an eight-step Fibonacci trace in F_97, the same field Ch 32’s FRI module uses. Its soundness section composes a per-stage budget and then multiplies it by the DFMS20-shaped factor stipulated here, which is where (2q + 1)^{2r} stops being an asymptotic shape and becomes one factor of the model’s QROM bound.
What Chapter 34 adds is the operator’s dial. Its Table 34.2 names seven parameter knobs, and the challenge space is one row among blowup factor, FRI query count, folding rounds, grinding bits, Merkle hash width, and trace length, each with an ethSTARK reference value. For FRI the present chapter sizes none of them, and no single knob sets the composed soundness on its own. Ch 35 then reads deployed pipelines against both chapters.
Exercises
Section titled “Exercises”E1. A PLONK-style protocol has r = 12 rounds. Per-round Fiat-Shamir challenges are drawn from |C| = 2^{128}, with interactive soundness eps_interactive = 1 / |C|^r. Target post-quantum soundness is 128 bits against a quantum adversary with query budget q = 2^{80}. Use the chapter’s stipulated model, (2q + 1)^{2r} * eps_interactive, to compute the compiled soundness error in bits, state whether the current challenge space is adequate under that model, and if not, derive the minimum per-round |C| it asks for.
E2. Classify Plonky3’s Fiat-Shamir structure into the three-tier scheme. Plonky3 uses a univariate STARK compiled with FRI at the inner layer and a polynomial commitment interface at the outer layer. Identify which tier each compilation step sits in and what the composed reduction looks like in terms of the per-tier losses under the chapter’s stipulated model, and say why that composition is not a certified QROM bound for Plonky3.
E3. State the classical rewinding argument for Schnorr: given two accepting Fiat-Shamir transcripts (a, e_1, z_1) and (a, e_2, z_2) with e_1 != e_2, derive the witness x. Identify the exact step in the argument that fails when the adversary’s access to H is via quantum queries. One sentence answer is acceptable.
E4. Apply the three-move bound epsilon_qrom <= (2q + 1)^2 * epsilon to a three-move protocol under an explicit assumption: that its interactive soundness error is epsilon = 1 / |C| against quantum dishonest provers. The assumption is the exercise’s premise, and it is what the bound needs. Computational special soundness does not supply it, for the reason the measure-and-reprogram section gives. Take the chapter’s toy Schnorr group for the transcript algebra, with subgroup order n = 1013 (so |C| = n) and quantum query budget q = 2^{16}. Show the resulting bound is vacuous (greater than 1). Then compute the minimum |C| required for the (2q + 1)^2 / |C| term to meet 80 bits of PQ soundness at the same q. State in bits how much the challenge space must grow beyond the toy n = 1013, and say what that width does not establish about Schnorr itself.
Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 33. A separate track, for rebuilding rather than reading: the package exercises/ch33-fiat-shamir-qrom has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch33 to grade your version against the suite that proves the reference one.
References
Section titled “References”Last updated: