The Complexity of Zero Knowledge

DOI10.1007/978-3-540-77050-3_5zbMATH Open1135.68444OpenAlexW1565801357MaRDI QIDQ5458822FDOQ5458822

Authors: Salil Vadhan 

Publication date: 24 April 2008

Published in: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77050-3_5

Recommendations

• The Knowledge Complexity of Interactive Proof Systems
• scientific article; zbMATH DE number 94166
• On the communication complexity of zero-knowledge proofs
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• scientific article; zbMATH DE number 3999326

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Title not available (Why is that?)
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• New directions in cryptography
• A Pseudorandom Generator from any One-way Function
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Interactive proofs and the hardness of approximating cliques
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Unconditional Study of Computational Zero Knowledge
• Bit commitment using pseudorandomness
• Minimum disclosure proofs of knowledge
• Perfect zero-knowledge arguments for NP using any one-way permutation
• The random oracle methodology, revisited.
• Statistically-hiding commitment from any one-way function
• Universal Arguments and their Applications
• Foundations of Cryptography
• On the Composition of Zero-Knowledge Proof Systems
• Non-deterministic exponential time has two-prover interactive protocols
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm
• Definitions and properties of zero-knowledge proof systems
• The Knowledge Complexity of Interactive Proof Systems
• Statistical zero-knowledge languages can be recognized in two rounds
• A complete problem for statistical zero knowledge
• Quantum lower bound for the collision problem
• Worst-Case to Average-Case Reductions Revisited
• Advances in Cryptology - CRYPTO 2003
• New and improved constructions of non-malleable cryptographic protocols
• Unconditional Characterizations of Non-interactive Zero-Knowledge
• On Worst‐Case to Average‐Case Reductions for NP Problems
• The complexity of computing a Nash equilibrium
• Algebraic methods for interactive proof systems
• IP = PSPACE
• On the power of multi-prover interactive protocols
• Computationally Sound Proofs
• Title not available (Why is that?)
• Adiabatic Quantum State Generation
• On relationships between statistical zero-knowledge proofs
• Zero knowledge with efficient provers
• Bounded-concurrent secure multi-party computation with a dishonest majority
• SZK Proofs for Black-Box Group Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Trading help for interaction in statistical zero-knowledge proofs
• Title not available (Why is that?)
• Theory of Cryptography
• On zero-knowledge proofs (extended abstract)
• Protocols for bounded-concurrent secure two-party computation in the plain model
• Zero Knowledge and Soundness Are Symmetric

Cited In (6)

• Provably Hard Zero-Way Functions
• Title not available (Why is that?)
• The round complexity of quantum zero-knowledge
• Title not available (Why is that?)
• Cryptography and zero knowledge
• QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge

This page was built for publication: The Complexity of Zero Knowledge

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458822)