Probabilistic Checking against Non-Signaling Strategies

针对非信号策略的概率检查

• 批准号: RGPIN-2019-06236
• 负责人: Shinkar, Igor
• 金额: $ 2.04万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750577
• 关键词: Probabilistic; Checking; against; Non; Signaling

Cloud computing is a paradigm that provides access to computational resources, such as storing data or performing complex computation, that are beyond the computational power of the user. In cloud computing the problem of delegating computation is concerned with the setting where a computationally weak device, the client (or the verifier), wishes to outsource a computational task to a powerful but untrusted party, the server (or the prover). Since the server can, potentially, err when performing the computation, it is required in addition to the answer to also provide a proof that the computation was done correctly. Naturally, we require that verifying this proof is significantly `easier' than doing the computation itself. That is, the running time of the client should be smaller than the time required to perform the computation without any additional help. Recently, motivated by the goal of constructing such delegation schemes, the notion of multi--prover interactive proof systems (MIPs) that are sound against non--signaling adversaries (nsMIPs) has been introduced. Non--signaling strategies have been studied in the quantum physics literature, and are strict generalization of quantum entangled strategies that consider all possible correlations under the minimal requirement that respects the ''no instantaneous communication'' principle in physics. Although in the recent years there has been some progress in constructing nsMIPs, our understanding of such proof systems remains limited. Indeed, while for classical proof systems we have a rich arsenal of tools and techniques, for non--classical proof systems many fundamental questions are still open, and the current techniques are relatively restricted. For example, the PCP Theorem (in the classical setting) says that for any language in NEXP there is a 1-round protocol between a polynomial time verifier and two non--communicating provers, where the verifier send random queries to the provers, each of the provers responds with a short message, allowing the verifier to decide with high probability whether a given input belongs to the language or not. In contrast, the (appropriately stated) non--signaling analogue of the PCP theorem is not known. The best known results in the non--signaling setting require a polynomial number of provers for any languages in EXP, but it may well be that three provers suffice as well. This project will contribute to the systematic study of the power and limitations of proof systems that are sound against non--signaling strategies. We will investigate fundamental problems related to non-signaling strategies, including studying property testing in the non-signaling setting  (such as low-degree testing), and apply theses techniques to obtain nsMIPs with optimal parameters. The research will show strong ties between Physics and Computing Science (most notably Complexity Theory and Cryptography), and will strengthen the connections between their scientific communities.

云计算是一种提供对计算资源的访问的范例，诸如存储数据或执行复杂计算，这些计算资源超出了用户的计算能力。在云计算中，委托计算的问题与计算能力弱的设备（客户端（或验证器））希望将计算任务外包给强大但不可信的一方（服务器（或证明器））的设置有关。由于服务器在执行计算时可能会出错，因此除了答案之外，还需要提供计算正确完成的证明。当然，我们要求验证这个证明比计算本身要“容易”得多。也就是说，客户端的运行时间应该小于在没有任何额外帮助的情况下执行计算所需的时间。最近，出于构建这样的委托方案的目标，多-prover交互式证明系统（MIP）的概念，是健全的对非-信令对手（nsMIP）已被引入。非信号策略已经在量子物理学文献中进行了研究，并且是量子纠缠策略的严格概括，该策略在尊重物理学中的“无瞬时通信”原则的最低要求下考虑所有可能的相关性。虽然近年来在构造nsMIP方面取得了一些进展，但我们对这种证明系统的理解仍然有限。事实上，虽然对于经典证明系统，我们有丰富的工具和技术，对于非经典证明系统，许多基本问题仍然是开放的，目前的技术相对有限。例如，PCP定理（在经典设置中）说，对于NEXP中的任何语言，在多项式时间验证者和两个非通信证明者之间存在1轮协议，其中验证者向证明者发送随机查询，每个证明者都用短消息响应，允许验证者以高概率决定给定输入是否属于该语言。相比之下，PCP定理的（适当陈述的）非信号模拟是未知的。在非信令设置中最著名的结果需要多项式数量的证明器用于EXP中的任何语言，但很可能三个证明器也足够了。这个项目将有助于系统地研究证据系统的力量和局限性，这些证据系统对非信号策略是健全的。我们将研究与非信号策略相关的基本问题，包括研究非信号设置中的属性测试（如低度测试），并应用这些技术获得具有最佳参数的nsMIP。该研究将显示物理学和计算科学之间的紧密联系（最明显的是复杂性理论和密码学），并将加强其科学界之间的联系。