Non-local Zero-Knowledge

非局部零知识

• 批准号: RGPIN-2021-03308
• 负责人: Crépeau, Claude
• 金额: $ 2.55万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=742488
• 关键词: 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.

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