On the complexity of interactive proofs with bounded communication
From MaRDI portal
Publication:293359
DOI10.1016/S0020-0190(98)00116-1zbMATH Open1338.68104DBLPjournals/ipl/GoldreichH98WikidataQ56959078 ScholiaQ56959078MaRDI QIDQ293359FDOQ293359
Authors: Oded Goldreich, Johan Hastad 
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
Recommendations
- Interactive proofs with approximately commuting provers
- scientific article; zbMATH DE number 512803
- scientific article; zbMATH DE number 176552
- scientific article; zbMATH DE number 31277
- On the communication complexity of zero-knowledge proofs
- A PCP theorem for interactive proofs and applications
- Interactive proof systems and alternating time-space complexity
- scientific article; zbMATH DE number 176510
- On interactive proofs with a laconic prover
- The Knowledge Complexity of Interactive Proof Systems
Cites Work
- Random generation of combinatorial structures from a uniform distribution
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Minimum disclosure proofs of knowledge
- The knowledge complexity of interactive proof-systems
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Does co-NP have short interactive proofs ?
- Uniform generation of NP-witnesses using an NP-oracle
Cited In (37)
- Title not available (Why is that?)
- Subquadratic SNARGs in the random oracle model
- Non-interactive proofs of proximity
- Succinct non-interactive arguments via linear interactive proofs
- Non-interactive batch arguments for NP from standard assumptions
- Witness-succinct universally-composable SNARKs
- Interactive proof systems and alternating time-space complexity
- On the (in)security of SNARKs in the presence of oracles
- Doubly efficient interactive proofs over infinite and non-commutative rings
- Impossibilities in succinct arguments: black-box extraction and more
- Interactive oracle proofs
- On interactive proofs with a laconic prover
- Predictable arguments of knowledge
- Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier
- Using fully homomorphic hybrid encryption to minimize non-interative zero-knowledge proofs
- Strong batching for non-interactive statistical zero-knowledge
- A direct product theorem for two-party bounded-round public-coin communication complexity
- Uniform generation of NP-witnesses using an NP-oracle
- On the P versus NP intersected with co-NP question in communication complexity
- Succinct arguments in the quantum random oracle model
- Incrementally verifiable computation via incremental PCPs
- Constant-round interactive proofs for delegating computation
- Title not available (Why is that?)
- Constant-round arguments from one-way functions
- Title not available (Why is that?)
- On the virtue of succinct proofs
- Constant-round arguments for batch-verification and bounded-space computations from one-way functions
- The hunting of the SNARK
- Round complexity versus randomness complexity in interactive proofs
- On transformation of interactive proofs that preserve the prover's complexity
- Polylogarithmic two-round argument systems
- Title not available (Why is that?)
- Interactive proofs and the hardness of approximating cliques
- Succinct interactive oracle proofs: applications and limitations
- The complexity of the max word problem and the power of one-way interactive proof systems
- A toolbox for barriers on interactive oracle proofs
- On succinct arguments and witness encryption from groups
This page was built for publication: On the complexity of interactive proofs with bounded communication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293359)
