A complete problem for statistical zero knowledge
From MaRDI portal
Publication:3455561
DOI10.1145/636865.636868zbMath1326.68165OpenAlexW2069170136WikidataQ21694677 ScholiaQ21694677MaRDI QIDQ3455561
Publication date: 7 December 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4728406
Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (46)
A black-box approach to post-quantum zero-knowledge in constant rounds ⋮ On Black-Box Extensions of Non-interactive Zero-Knowledge Arguments, and Signatures Directly from Simulation Soundness ⋮ Complete Problem for Perfect Zero-Knowledge Quantum Proof ⋮ The Untold Story of $$\mathsf {SBP}$$ ⋮ A Surprisingly Simple Way of Reversing Trace Distance via Entanglement ⋮ Statistical Randomized Encodings: A Complexity Theoretic View ⋮ New Limits to Classical and Quantum Instance Compression ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ AND-compression of NP-complete problems: streamlined proof and minor observations ⋮ On the complexity of collision resistant hash functions: new and old black-box separations ⋮ Statistical difference beyond the polarizing regime ⋮ Statistical zero knowledge and quantum one-way functions ⋮ Super-Perfect Zero-Knowledge Proofs ⋮ How to eat your entropy and have it too: optimal recovery strategies for compromised RNGs ⋮ The final nail in the coffin of statistically-secure obfuscator ⋮ Unnamed Item ⋮ Public-key encryption from homogeneous CLWE ⋮ Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations ⋮ Structure Versus Hardness Through the Obfuscation Lens ⋮ A framework for non-interactive instance-dependent commitment schemes (NIC) ⋮ On the complexity of compressing obfuscation ⋮ Lower bounds for non-black-box zero knowledge ⋮ Perfect Non-interactive Zero Knowledge for NP ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ How to Achieve Perfect Simulation and A Complete Problem for Non-interactive Perfect Zero-Knowledge ⋮ General Properties of Quantum Zero-Knowledge Proofs ⋮ Cryptography and Game Theory: Designing Protocols for Exchanging Information ⋮ An Equivalence Between Zero Knowledge and Commitments ⋮ On the relationship between statistical zero-knowledge and statistical randomized encodings ⋮ Placing conditional disclosure of secrets in the communication complexity universe ⋮ How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge ⋮ The Complexity of Zero Knowledge ⋮ On best-possible obfuscation ⋮ Новые оценки расстояния по вариации между двумя распределениями выборки ⋮ Оценки расстояния по вариации между распределениями двух наборов независимых случайных величин ⋮ Public-coin statistical zero-knowledge batch verification against malicious verifiers ⋮ On the Relationship Between Statistical Zero-Knowledge and Statistical Randomized Encodings ⋮ Quantum computing and hidden variables ⋮ Unnamed Item ⋮ Communication Complexity of Statistical Distance ⋮ Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments ⋮ Robust characterizations of k -wise independence over product spaces and related testing results
This page was built for publication: A complete problem for statistical zero knowledge
