Paper 2023/1256

On Soundness Notions for Interactive Oracle Proofs

Alexander R. Block, Georgetown University, University of Maryland, College Park
Albert Garreta, Nethermind Research
Pratyush Ranjan Tiwari, Johns Hopkins University
Michał Zając, Nethermind Research

Interactive oracle proofs (IOPs) (Ben-Sasson et al., TCC 2016; Reingold et al., SICOMP 2021) have emerged as a powerful model for proof systems combining IP and PCP. While IOPs are not any more powerful than PCPs from a complexity theory perspective, their potential to create succinct proofs and arguments has been demonstrated by many recent constructions achieving better parameters such as total proof length, alphabet size, and query complexity. In this work, we establish new results on the relationship between various notions of soundness for IOPs. First, we formally generalize the notion of round-by-round soundness (Canetti et al., STOC 2019) and round-by-round knowledge soundness (Chiesa et al., TCC 2019). Given this generalization, we then examine its relationship to the notions of generalized special soundness (Attema et al., CRYPTO 2021) and generalized special unsoundness (Attema et al., TCC 2022). We show that: 1. generalized special soundness implies generalized round-by-round soundness; 2. generalized round-by-round knowledge soundness implies generalized special soundness; 3. generalized special soundness does not imply generalized round-by-round knowledge soundness; 4. generalized round-by-round soundness (resp., special unsoundness) is an upper bound (resp., a lower bound) on standard soundness, and this relationship is tight when the round-by-round soundness and special unsoundness errors are equal; and 5. any special sound IOP can be transformed via (a variant of) the Fiat-Shamir transformation (in the Random Oracle Model) into a non-interactive proof that is adaptively sound in the Quantum Random Oracle Model.

Note: Fixed multiple typos and restructured later sections.

Available format(s)
Cryptographic protocols
Publication info
Fiat-Shamir TransformationSpecial SoundnessRound-by-round SoundnessPost-Quantum Security
Contact author(s)
alexander r block @ gmail com
albert @ nethermind io
pratyush @ cs jhu edu
michal @ nethermind io
2023-09-08: revised
2023-08-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexander R. Block and Albert Garreta and Pratyush Ranjan Tiwari and Michał Zając},
      title = {On Soundness Notions for Interactive Oracle Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1256},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.