Spatial Isolation Implies Zero Knowledge Even in a Quantum World

DOI10.1145/3511100MaRDI QIDQ5066952zbMATH OpenOpenAlexWikidataFDO

Authors Alessandro Chiesa, Tom Gur, Nicholas Spooner, Michael A. Forbes

Publication date 31 March 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/130726/1/WRAP-spatial-isolation-zero-quantum-world-Gur-2019.pdf

zbMATH Keywords

algebraic complexityinteractive PCPsmulti-prover interactive proofsquantum entangled strategiessumcheck protocolzero knowledge

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Practical relativistic zero-knowledge for NP
• Algorithms and Computation
• Zero-knowledge proof systems for QMA

Cites work

• Advances in Cryptology – CRYPTO 2004
• Algebraic methods for interactive proof systems
• Algebrization: a new barrier in complexity theory
• Algorithms and Computation
• Coding theorem and strong converse for quantum channels
• Constant-round interactive proofs for delegating computation
• Definitions and properties of zero-knowledge proof systems
• Delegating computation: interactive proofs for muggles
• Deterministic polynomial identity testing in non-commutative models
• Does co-NP have short interactive proofs ?
• Entangled games are hard to approximate
• General Properties of Quantum Zero-Knowledge Proofs
• scientific article; zbMATH DE number 4191106 (Why is no real title available?)
• scientific article; zbMATH DE number 4195163 (Why is no real title available?)
• scientific article; zbMATH DE number 1302864 (Why is no real title available?)
• scientific article; zbMATH DE number 708807 (Why is no real title available?)
• scientific article; zbMATH DE number 1559565 (Why is no real title available?)
• scientific article; zbMATH DE number 7250160 (Why is no real title available?)
• Interactive locking, zero-knowledge PCPs, and unconditional cryptography
• Interactive PCP
• IP = PSPACE using error-correcting codes
• Making Good Codes for Classical-Quantum Channel Coding via Quantum Hypothesis Testing
• Non-deterministic exponential time has two-prover interactive protocols
• Non-interactive zero-knowledge proofs in the quantum random oracle model
• Parallel repetition of entangled games
• Power sums over finite subspaces of a field
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Quantum proofs of knowledge
• Quasi-linear size zero knowledge from linear-algebraic PCPs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robust locally testable codes and products of codes
• Statistical zero-knowledge languages can be recognized in two rounds
• The black-box query complexity of polynomial summation
• The Knowledge Complexity of Interactive Proof Systems
• Zero knowledge protocols from succinct constraint detection

Cited in

(4)

• On succinct non-interactive arguments in relativized worlds
• The round complexity of quantum zero-knowledge
• Practical relativistic zero-knowledge for NP
• Streaming zero-knowledge proofs

This page was built for publication: Spatial Isolation Implies Zero Knowledge Even in a Quantum World

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