Paper 2019/871
Non-Locality and Zero-Knowledge MIPs
Claude Crépeau and Nan Yang
Abstract
The foundation of zero-knowledge is the simulator: a weak machine capable of pretending to be a weak verifier talking with all-powerful provers. To achieve this, simulators need some kind of advantage such as the knowledge of a trapdoor. In existing zero-knowledge multi-prover protocols, this advantage is essentially signalling, something that the provers are explicitly forbidden to do. In most cases, this advantage is stronger than necessary as it is possible to define a sense in which simulators need much less to simulate. We define a framework in which we can quantify the simulators’ non-local advantage and exhibit examples of zero-knowledge protocols that are sound against local or entangled provers but that are not sound against no-signalling provers precisely because the no-signalling simulation strategy can be adopted by malicious provers.
Note: Submitted to TCC-2019.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. quant-ph arXiv
- Keywords
- Zero-KnowledgeMulti-Prover proofs
- Contact author(s)
- claude crepeau @ mcgill ca
- History
- 2019-07-30: received
- Short URL
- https://ia.cr/2019/871
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/871,
author = {Claude Crépeau and Nan Yang},
title = {Non-Locality and Zero-Knowledge MIPs},
howpublished = {Cryptology ePrint Archive, Paper 2019/871},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/871}},
url = {https://eprint.iacr.org/2019/871}
}
