Probabilistic Checking against Non-Signaling Strategies

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

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.