Grant: Discovery Grants Program - Individual
McGill University
$35,000.00
Non-local Zero-Knowledge
EF 2021-22
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2021-03308
Name nom
Crépeau, Claude
Department département
Computer Science, School of - Computer Science, School of
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2021
Competition year année de concours
2021
Award amount
35000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
800
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information and communication services
Area of application fr
Services d'information et de télé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
Installment
inst:1
Partie
1
Nb partie
5
Application title
Non-local Zero-Knowledge
Keyword
NSERC
Application summary
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.