Probabilistic Checking against Non-Signaling Strategies

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

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

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