On the complexity of interactive proofs with bounded communication
From MaRDI portal
Publication:293359
DOI10.1016/S0020-0190(98)00116-1zbMath1338.68104WikidataQ56959078 ScholiaQ56959078MaRDI QIDQ293359
Oded Goldreich, Johan T. Håstad
Publication date: 9 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001161?np=y
Related Items
Subquadratic SNARGs in the random oracle model, Succinct non-interactive arguments via linear interactive proofs, Non-interactive batch arguments for NP from standard assumptions, On the (In)Security of SNARKs in the Presence of Oracles, Interactive Oracle Proofs, Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier, Succinct arguments in the quantum random oracle model, Incrementally verifiable computation via incremental PCPs, Witness-succinct universally-composable SNARKs, Succinct interactive oracle proofs: applications and limitations, Using fully homomorphic hybrid encryption to minimize non-interative zero-knowledge proofs, A toolbox for barriers on interactive oracle proofs, The hunting of the SNARK, Impossibilities in succinct arguments: black-box extraction and more, Non-interactive proofs of proximity, Predictable Arguments of Knowledge, Polylogarithmic two-round argument systems, Unnamed Item, Constant-Round Interactive Proofs for Delegating Computation, On succinct arguments and witness encryption from groups, Uniform generation of NP-witnesses using an NP-oracle
Cites Work
- Random generation of combinatorial structures from a uniform distribution
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Does co-NP have short interactive proofs ?
- Minimum disclosure proofs of knowledge
- Uniform generation of NP-witnesses using an NP-oracle
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- The knowledge complexity of interactive proof-systems
