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 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-based SNARKs have an asymptotic QROM Fiat-Shamir bound (Block et al. 2023) inherited via the Ben-Sasson-Chiesa-Spooner (BCS) state-restoration lift, plus a deployment-parameter concrete-security audit in the classical ROM (Block-Tiwari 2024). A deployment-parameter QROM audit at the parameters of ethSTARK, Plonky2, or Starknet remains open.
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 derives each tier’s QROM reduction and states the concrete parameter cost a deployment pays to absorb the reduction loss.
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, inherited via the BCS state-restoration lift from FRI’s round-by-round soundness, with explicit bounds against quantum-query adversaries for FRI and batched FRI (Block et al., 2023). Block-Tiwari 2024 then audit the concrete security of the same Fiat-Shamir compilation in the classical ROM at deployed parameter settings (Plonky2, stone-prover, SHARP (StarkWare’s shared prover), dYdX, Miden, RISC Zero, era-boojum). They report provable security 21 to 63 bits below conjectured security in all but one of the surveyed sets (Block & Tiwari, 2024). A concrete-parameter QROM accounting at any one production pipeline that composes interactive FRI soundness, Fiat-Shamir loss, Merkle binding, hash-output width, grinding, recursion, and per-system parameter choices is not in the literature as of 2026.
A Schnorr proof compiled three ways
Section titled “A Schnorr proof compiled three ways”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, h) in the multiplicative group F_p^*. A zero witness x = 0 is excluded only because it would force the public key h = 1 and trivialize the relation. 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 toy code below also enforces r != 0, which is harmless at the size of n but not required by the protocol definition. The verifier picks a challenge e uniformly in Z_n and sends it. The prover sends the response z = (r + e * x) mod n. 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.
This is a public-coin three-move protocol: the verifier’s challenge depends on no prover-chosen randomness beyond the first message. Classical 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). Substituting an interactive soundness error epsilon = 1 / |C| for Schnorr, which has to hold against the quantum prover the reduction produces (the measure-and-reprogram section below says why), gives epsilon_qrom <= (2q + 1)^2 / |C|, the form the rest of this chapter sizes parameters against. Read that as the best case rather than as a safety margin: every sigma protocol has epsilon >= 1 / |C|, and one whose interactive soundness exceeds the floor pays the same factor on the larger number.
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. 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. 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. The underlying knowledge soundness of the Schnorr identification scheme is tied to discrete logarithm hardness in the group, but the same-challenge response-uniqueness condition itself is not merely a DLP reduction.
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, it gives a tight reduction from Module-LWE for a modified Dilithium-QROM variant whose identification scheme admits lossy keys, and 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, so that the deterministic scheme is UF-CMA secure in the QROM under Module-LWE and SelfTargetMSIS together (Kiltz et al., 2018, sec. 1.1). DFMS19 treats the same 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 DFMS19 (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 dedicated security analyses that exploit the protocol’s structure (round-by-round soundness composed via the BCS state-restoration argument), 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 the 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 QROM result is inherited via the BCS state-restoration lift from FRI’s round-by-round soundness, which is independently of cryptographic interest because BCS-compiled, round-by-round-sound IOPs lift unconditionally into the QROM. Explicit 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 parameter settings (Plonky2, stone-prover, SHARP, dYdX, Miden, RISC Zero, era-boojum) and the lambdaworks library, and 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. They also give parameter guidelines that recover 100-bit provable security at specific blowup, query-count, and grinding configurations. 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 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: security against superposition queries to the permutation is outside the model and is not established for sponge-based deployed Fiat-Shamir. 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 every Fiat-Shamir result in this chapter. 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 arises from the hybrid’s two-option selector at each index position.
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. DFMS19 is explicit that classical special soundness does not supply it: “in the quantum setting, special soundness does not imply ordinary soundness”, and its signature result asks for “a proof-of-knowledge against quantum dishonest provers” (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.
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”The QROM reduction loss translates into concrete parameter bumps at deployment. 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 |
|---|---|---|---|
| Three-move sigma (DFMS19) | 2 log_2(2q + 1) + k, just above 290.0 | 291 bits | 2 q_bits + k = 288, short by 3 |
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 |
| FRI / BCS SNARK | dedicated FRI bound, not this formula | not derived here | generic DFMS20 model does not apply |
Both expressions sit 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, and 172.67 rules out 172. 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 |
|---|---|---|---|
| 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 |
| 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) |
| FRI / BCS-based SNARK | Dedicated FRI Fiat-Shamir analysis (Block et al. 2023, ASIACRYPT 2023); BCS lift gives QROM bound 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 |
In Table 33.2’s FRI row, q and kappa are the chapter’s standard parameters. 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 (Block et al. 2023) and a concrete-parameter audit in the classical ROM (Block-Tiwari 2024). A concrete deployment-parameter QROM audit at the parameters of any one production FRI pipeline (ethSTARK, Plonky2, Starknet, Plonky3) requires composing the FRI Fiat-Shamir bound with Merkle binding, hash-output width, grinding bits, recursion, and per-system parameter choices. That composed analysis remains system-specific as of 2026.
The operator decision is to place the candidate deployment in one of the three rows and size the challenge space, round count, or repetition to absorb the reduction loss at the target PQ bit margin.
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 the state-restoration lift 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 exploits FRI’s round-by-round soundness and the BCS state-restoration lift (Block et al., 2023). 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 grinding counted and with batching, larger folds and recursion deliberately left out, and reports 21 to 63 bit gaps between provable and conjectured security in all but one of the surveyed deployed configurations (Block & Tiwari, 2024, sec. 3.3). 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, read off the reduction loss, and size the challenge space, round count, and grinding bits to absorb the loss at the target post-quantum bit margin.
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 the same tier, 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). 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 priced off the shelf by DFMS20, and its 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 is published (Block et al. 2023). Concrete-parameter analysis at deployment scale is published in the classical ROM (Block-Tiwari 2024) and reports 21 to 63 bit gaps below conjectured security in all but one of the surveyed deployed configurations. A deployment-parameter QROM audit at production-pipeline scale is not in the literature as of 2026 (Block et al., 2023; Block & Tiwari, 2024; Chiesa & Orrù, 2025).
The operator response is not a parameter bump today. It is the governance-multisig upgrade path that any of these rollups already carries for unrelated reasons. Block-Tiwari 2024 already supplies parameter guidelines that recover 100-bit provable security at specific blowup, query-count, and grinding configurations. Once a deployment-parameter QROM analysis at production-pipeline scale is published, the multisig activates a parameter or scheme change. 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 priced each one. 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 classical 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 is sized under a dedicated bound rather than the generic DFMS20 form, and 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 chapter composes a per-stage budget and then multiplies by the DFMS20-shaped factor stipulated here, which is where (2q + 1)^{2r} stops being an asymptotic shape and becomes one term in a sum.
What Chapter 34 adds is the operator’s dial. Its Table 34.2 names seven parameter knobs, and the challenge space |C| sized here 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. Sizing the challenge space is necessary and nowhere near sufficient. 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. Classical 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: