Round-by-round soundness
The per-round invariant that decides what Fiat-Shamir preserves
Motivation
Fiat–Shamir turns an interactive public-coin proof into a non-interactive argument by deriving the verifier’s messages from a hash of the transcript so far. Ordinary soundness is not what survives that transformation. What survives is a stronger, more local property: there is a set of “doomed” partial transcripts, containing every false statement’s empty transcript, from which the prover escapes with probability at most \(\varepsilon\) per round, and from which a complete transcript is always rejected. That is round-by-round soundness, and the bits of security a Fiat–Shamir’ed argument achieves are governed by \(\log(1/\varepsilon)\) for that \(\varepsilon\) — not by the protocol’s ordinary soundness error.
Which makes one question immediately practical. Ordinary soundness amplifies cheaply: run copies in parallel. Does round-by-round soundness? If it does, then security can be bought with repetitions rather than with larger fields, longer challenges, or — in the approximate setting — more numerical precision.
Provenance and history
Round-by-round soundness was introduced by Canetti, Chen, Holmgren, Lombardi, Rothblum, Rothblum and Wichs (STOC 2019) and developed by Holmgren, who related it to state-restoration soundness. The transfer theorem — round-by-round error \(\varepsilon_{\mathrm{RBR}}\) gives Fiat–Shamir soundness \(O(Q\varepsilon_{\mathrm{RBR}} + Q^2 2^{-\kappa})\) against \(Q\) oracle queries — is the reason the notion is tracked at all, and it is assembled from Ben-Sasson, Chiesa and Spooner, the STOC 2019 paper, and Block, Garreta, Tiwari and Zajac.
The amplification question on this hub is raised by Bitan, DeStefano, Goldwasser, Ishai, Kalai and Thaler, Sum-check Protocol for Approximate Computations (IACR ePrint 2025/2152), as a remark immediately after the round-by-round analysis of their approximate sum-check protocol. They have a specific stake in it: their protocol achieves round-by-round soundness roughly \(\varepsilon^{2/r}\), an intermediate regime they argue is inherent to approximate computation, and repetition would be a way to reach a target security level without raising the precision of individual instances. They note the conjecture is known in one case only — where the protocol’s ordinary and round-by-round errors are maximally separated.
Parameter lattice
The separation between ordinary and round-by-round soundness against what is known about amplification.
| Regime | Example | \((k\cdot r)\)-fold repetition gives \(\varepsilon^k\)? |
|---|---|---|
| Maximally separated, \(\varepsilon_{\mathrm{RBR}} \approx \varepsilon_{\mathrm{sound}}^{1/r}\) | — | known (Canetti et al., Corollary 5.7) |
| Intermediate, \(\varepsilon_{\mathrm{RBR}} \approx \varepsilon^{2/r}\) | the source’s approximate sum-check over \(\mathbb{C}\) | c/0077 — open |
| Essentially coinciding | classical sum-check: \(\varepsilon_{\mathrm{RBR}} = d/q\), ordinary \(vd/q\) | c/0077 — open |