On the complexity of interactive proofs with bounded communication

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

zbMATH Keywords

computational complexicity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20)

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