Non-Locality and Zero-Knowledge MIPs
This work addresses foundational issues in cryptographic protocol design, specifically for zero-knowledge proofs, but appears incremental as it builds on existing frameworks to refine simulation strategies.
The paper tackles the problem of quantifying the non-local advantage needed for simulators in zero-knowledge multi-prover protocols, showing that existing protocols often require more advantage than necessary and providing examples where soundness fails against no-signalling provers due to this advantage.
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.