On Soundness Notions for Interactive Oracle Proofs

Alexander R. Block; Albert Garreta; Pratyush Ranjan Tiwari; Michał Zając

Paper 2023/1256

On Soundness Notions for Interactive Oracle Proofs

Alexander R. Block

, Georgetown University, University of Maryland, College Park

Albert Garreta, Nethermind Research, Basque Center of Applied Mathematics (BCAM)

Pratyush Ranjan Tiwari, Johns Hopkins University

Michał Zając, Nethermind Research

Abstract

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: Accidentally added publication details that were incorrect.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
DOI: 10.1007/978-981-99-8724-5_1
Keywords: Fiat-Shamir Transformation Special Soundness Round-by-round Soundness Post-Quantum Security
Contact author(s): alexander r block @ gmail com
albert @ nethermind io
pratyush @ cs jhu edu
michal @ nethermind io
History: 2024-03-05: last of 5 revisions; 2023-08-19: received; See all versions
Short URL: https://ia.cr/2023/1256
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1256,
      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},
      doi = {10.1007/978-981-99-8724-5_1},
      note = {\url{https://eprint.iacr.org/2023/1256}},
      url = {https://eprint.iacr.org/2023/1256}
}