Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
From MaRDI portal
Publication:4302852
DOI10.1145/116825.116852zbMath0799.68101WikidataQ55879618 ScholiaQ55879618MaRDI QIDQ4302852
Oded Goldreich, Avi Wigderson, Silvio Micali
Publication date: 24 November 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/116825.116852
interactive proofs; zero-knowledge proofs; information hiding; graph isomorphism; graph nonisomorphism; secure encryption
68R10: Graph theory (including graph drawing) in computer science
68P25: Data encryption (aspects in computer science)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, 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 Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization, The Complexity of Zero Knowledge, Locally random reductions: Improvements and applications, A language-dependent cryptographic primitive, Privacy-preserving algorithms for distributed mining of frequent itemsets, Complexity results in graph reconstruction, Practic zero-knowledge proofs: Giving hints and using deficiencies, An almost-constant round interactive zero-knowledge proof, A uniform-complexity treatment of encryption and zero-knowledge, On the communication complexity of zero-knowledge proofs, A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm, Zero knowledge and the chromatic number, Randomness in interactive proofs, The random oracle hypothesis is false, The knowledge complexity of quadratic residuosity languages, On the power of multi-prover interactive protocols, Practical proofs of knowledge without relying on theoretical proofs of membership on languages, Inverting onto functions., On the limits of nonapproximability of lattice problems, Interactive and probabilistic proof-checking, New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes., Fast approximate probabilistically checkable proofs, Lower bounds for non-black-box zero knowledge, Proving possession of arbitrary secrets while not giving them away: New protocols and a proof in GNY logic, Unclonable Group Identification
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Constant-round perfect zero-knowledge computationally convincing protocols
- Bit commitment using pseudorandomness
- Minimum disclosure proofs of knowledge
- Definitions and properties of zero-knowledge proof systems
- How to construct constant-round zero-knowledge proof systems for NP
- 2-round zero knowledge and proof auditors
- The Knowledge Complexity of Interactive Proof Systems
- Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Foundations of Cryptography
- On the Composition of Zero-Knowledge Proof Systems
- Zaps and Their Applications
- Theory of Cryptography
