Non-local Zero-Knowledge

零知识(ZK)证明的规范应用是用户向ATM识别，通常在用户和终端之间不存在信任的远程位置。对于高级别的安全性，统计ZK是我们追求的终极属性。强有力的证据表明，许多问题在SZK中是不能证明的，包括所有的NP-完全问题。为了实现SZK，引入了多证明者ZK证明的概念。通过让多个(非通信的)证明者与一个验证者交互，有可能为更多的问题提供SZK证明。“不交流”的概念相当微妙。这些词最初的意思是“仅限于当地的关联”。物理学的发展澄清了非定域性和无信号(NS)关联的概念。前者是通过纠缠实现的：量子力学使我们的世界变得更加局部化。然而，我们目前没有证据表明纠缠以外的关联可以比光速更快地产生(C)。狭义相对论是围绕这样一个原则发展起来的，即通信不能比c更快发生。然而，物理学中没有公认的原理表明，比信号更弱的关联不可能比c更快。目前尚不清楚我们的世界是否允许这种关联瞬间发生。在相对论ZK的背景下，不仅有众多的证明者，而且还有几个证明者。为了保证验证者之间的距离，我们将验证者放置在彼此已知距离的位置，并测量验证者的响应时间。通过这样做，他们可以验证证明者不可能进行沟通，因为无论他们在哪里，他们的反应都足够快。ZK的定义是指被称为法官的第三方，该第三方试图确定验证者是否真的与证明者互动，或者他报告的是否是假的。在相对论的背景下，有几个验证者的事实促使了对ZK概念的修订。首席法官可以将PUISNE法官放在审核员旁边，以确定他们是否与审核人交谈。这样的判决器可以区分在单个验证器/判决器场景中否则无法区分的情况。想象一下这样一种情况：信令验证器可以创建模拟，但NS验证器不能。在这种情况下，评审组将确信验证者实际上与证明者交谈，因为没有已知的模拟策略可以避免发送信号。非本地ZK是在多验证者/判断场景的背景下分析的，在该场景中，我们量化了各方的非本地。特别是，如果验证者可以使用较低形式的非局域性(例如量子纠缠或NS)来模拟他们与证明者的对话，那么产生的ZK比模拟需要模拟器之间的信令的情况更强。研究方案将探讨这一(未公布的)新定义的各个方面。

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.