The Complexity of Zero Knowledge

DOI10.1007/978-3-540-77050-3_5MaRDI QIDQ5458822zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(6)

• Provably Hard Zero-Way Functions
• scientific article; zbMATH DE number 708820 (Why is no real title available?)
• The round complexity of quantum zero-knowledge
• scientific article; zbMATH DE number 2196514 (Why is no real title available?)
• 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)