Welcome to the resource topic for 2023/1256
Title:
On Soundness Notions for Interactive Oracle Proofs
Authors: Alexander R. Block, Albert Garreta, Pratyush Ranjan Tiwari, Michał Zając
Abstract:Interactive oracle proofs (IOPs) (Ben-Sasson et al., TCC 2016) have emerged as a powerful model for proof systems which generalizes both Interactive Proofs (IPs) and Probabilistically Checkable Proofs (PCPs). 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 that 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 into a non-interactive proof that is adaptively sound in the Quantum Random Oracle Model.
ePrint: https://eprint.iacr.org/2023/1256
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .