Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-030 | 19th February 2019 17:37

Non-Locality in Interactive Proofs

RSS-Feed




TR19-030
Authors: Claude Crépeau, Nan Yang
Publication: 3rd March 2019 17:46
Downloads: 746
Keywords: 


Abstract:

In multi-prover interactive proofs (MIPs), the verifier is usually non-adaptive. This stems from an implicit problem which we call “contamination” by the verifier. We make explicit the verifier contamination problem, and identify a solution by constructing a generalization of the MIP model. This new model quantifies non-locality as a new dimension in the characterization of MIPs. A new property of zero-knowledge emerges naturally as a result by also quantifying the non-locality of the simulator.



ISSN 1433-8092 | Imprint