Statistical zero-knowledge languages can be recognized in two rounds

DOI10.1016/0022-0000(91)90006-QzbMath0732.68038WikidataQ56959192 ScholiaQ56959192MaRDI QIDQ808692

William Aiello, Johan T. Håstad

Publication date: 1991

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

interactive proof; zero-knowledge proof; class IP; hierarchy of probabilistic complexity classes; interactive prover-verifier pair

Mathematics Subject Classification ID

68P25: Data encryption (aspects in computer science)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

How to Achieve Perfect Simulation and A Complete Problem for Non-interactive Perfect Zero-Knowledge, General Properties of Quantum Zero-Knowledge Proofs, An Equivalence Between Zero Knowledge and Commitments, The Complexity of Zero Knowledge, A language-dependent cryptographic primitive, A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm, Definitions and properties of zero-knowledge proof systems, Practical proofs of knowledge without relying on theoretical proofs of membership on languages, Interactive and probabilistic proof-checking, Uniform generation of NP-witnesses using an NP-oracle, On relationships between statistical zero-knowledge proofs, Perfect Non-interactive Zero Knowledge for NP

Cites Work

• Unnamed Item
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• Universal classes of hash functions
• The Knowledge Complexity of Interactive Proof Systems
• The knowledge complexity of interactive proof-systems