Non-local Zero-Knowledge

点击翻译按钮获取中文摘要

The canonical application of Zero-Knowledge(ZK) proofs is that of a user identifying to an ATM, typically in a remote location where no trust exists between the user and the terminal. For high level of security, statistical ZK is the ultimate property we seek. Strong evidence suggests that many problems cannot be proved in SZK, including all NP-complete ones. In order to achieve SZK, the notion of multi-prover ZK proofs has been introduced. By having multiple (non-communicating) provers interact with a verifier, it is possible to have SZK proofs for many more problems. The notion of "non-communicating" is rather subtle. These words originally meant "limited to LOCAL correlations." Developments in physics have clarified the notions of non-locality and No-Signalling(NS) correlations. The former is achieved via entanglement: Quantum mechanics makes our world more than LOCAL. However, we currently have no evidence that correlations beyond entanglement can be produced faster than the speed of light (c). Special Relativity is developed around the principle that communication cannot happen faster than c. Nevertheless, there is no accepted principle in physics stating that correlations weaker than signalling cannot travel faster than c. It is currently unknown whether our world allows such correlations instantaneously. In the setting of Relativistic ZK, not only are there numerous provers but also several verifiers. In order to guarantee distance between the provers we position the verifiers at known distance from each other and measure the response time of the provers. By doing so they can validate that the provers cannot possibly have communicated because they responded fast enough WHEREVER THEY WERE. ZK is defined in reference to a third party called the judge who is trying to establish whether the verifier actually interacted with a prover or whether what he reported was fake. In the relativistic setting the fact that there are several verifiers motivates a revision of the notion of ZK. A chief judge can position puisne judges next to the verifiers so to determine whether they talked to provers or not. It is possible that such judges can distinguish situations that are otherwise undistinguishable in a single verifier/judge scenario. Imagine a situation where signalling verifiers can create a simulation but NS verifiers cannot. In such a case, the group of judges would be convinced that the verifiers actually spoke to the provers because no known simulation strategy avoids signalling. Non-local ZK is analyzed in the context of a multi-verifier/judge scenario where we quantify the non-locality of the parties. In particular, if verifiers can simulate their conversations with provers using a lower form of non--locality (quantum entanglement or NS for instance) then the resulting ZK is stronger than the case where simulation requires signalling among the simulators. The research programme will explore various aspects of this (unpublished) new definition.