Grant: Discovery Grants Program - Individual
Simon Fraser University
$56,000.00
Probabilistic Checking against Non-Signaling Strategies
FY 2024-25
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2019-06236
Name nom
Shinkar, Igor
Department département
Computing Science
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2019
Award amount
56000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Probabilistic Checking against Non-Signaling Strategies
Keywords
proof systems; probabilistically checkable proofs; delegation of computation; non-signaling strategies; property testing
Application summary
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.