A Study of Non-Local Strategies for Zero-Knowledge Proof Systems

Abstract

No-signalling (NOSIG) correlations, that are stronger than those allowed by quantum entanglement yet do not violate relativistic causality, are a valuable resource for understanding information processing systems. Such correlations can be achieved between non-communicating players in games when the players use what is called non-local strategies, and can give the players better odds at winning in these games. We propose definitions for non-local strategies in relativistic multi-player non-local games. We prove a conjecture by Crépeau stating that any non-local strategy that can be simultaneously produced by any pi-signalling strategy in a multi-player non-local game, has to be a NOSIG strategy. Pi-signalling strategies are achieved when 1-way signalling is allowed between players arranged on a line defined by some permutation. This result gives us a better understanding of how NOSIG strategies fit with the other non-local strategies, and can help in constructing novel NOSIG multi-player strategies and help prove they produce NOSIG correlations. Finally, we extend the definition of zero-knowledge proof systems to the relativistic multi-prover, multi-verifier setting, and propose definitions for what it means for a non-local strategy to have polynomial time complexity