On the Power of Statistical Zero Knowledge

DOI10.1137/17M1161749zbMath1452.68081arXiv1609.02888OpenAlexW2981825888WikidataQ126978270 ScholiaQ126978270MaRDI QIDQ5117376

Prashant Nalini Vasudevan, Adam Bouland, Justin Thaler, Dhiraj Holden, Lijie Chen

Publication date: 25 August 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1609.02888

zbMATH Keywords

hardness amplificationoracle separationperfect zero-knowledge proofstatistical zero-knowledge proof

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Communication complexity, information complexity (68Q11)

Related Items (10)

The Untold Story of $$\mathsf {SBP}$$ ⋮ Approximate Degree in Classical and Quantum Computing ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Statistical difference beyond the polarizing regime ⋮ Unnamed Item ⋮ Placing conditional disclosure of secrets in the communication complexity universe ⋮ Public-coin statistical zero-knowledge batch verification against malicious verifiers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic communication complexity
• Statistical zero-knowledge languages can be recognized in two rounds
• Relativized perfect zero knowledge is not BPP
• Does co-NP have short interactive proofs ?
• The random oracle hypothesis is false
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• On the impossibility of entropy reversal, and its application to zero-knowledge proofs
• The unbounded-error communication complexity of symmetric functions
• How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge
• The Space "Just Above" BQP
• Bounded Indistinguishability and the Complexity of Recovering Secrets
• Algebrization
• Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication
• The Sign-Rank of AC$^0$
• Quantum computing and hidden variables
• The Pattern Matrix Method
• PP is as Hard as the Polynomial-Time Hierarchy
• Statistical Randomized Encodings: A Complexity Theoretic View
• Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
• Quantum lower bounds for the collision and the element distinctness problems
• Learning Complexity vs Communication Complexity
• Quantum lower bound for the collision problem
• Noninteractive Statistical Zero-Knowledge Proofs for Lattice Problems
• The Knowledge Complexity of Interactive Proof Systems
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Improved Bounds on the Sign-Rank of AC^0
• The Landscape of Communication Complexity Classes.
• Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation
• Balls and bins: A study in negative dependence
• Breaking the minsky-papert barrier for constant-depth circuits
• Bounded Independence Fools Halfspaces
• Estimating the unseen

This page was built for publication: On the Power of Statistical Zero Knowledge