Paper 2018/326

Verifier Non-Locality in Interactive Proofs

Claude Crepeau and Nan Yang


In multi-prover interactive proofs, the verifier interrogates the provers and attempts to steal their knowledge. Other than that, the verifier's role has not been studied. Augmentation of the provers with non-local resources results in classes of languages that may not be NEXP. We have discovered that the verifier plays a much more important role than previously thought. Simply put, the verifier has the capability of providing non-local resources for the provers intrinsically. Therefore, standard MIPs may already contain protocols equivalent to one in which the prover is augmented non-locally. Existing MIPs' proofs of soundness implicitly depend on the fact that the verifier is not a non-local resource provider. The verifier's non-locality is a new unused tool and liability for protocol design and analysis. Great care should have been taken when claiming that ZKMIP=MIP. We show specific issues with existing protocols and revisit the proof of this statement. For this purpose, we also define a new model of multi-prover interactive proofs which we call "correlational confinement form".

Note: Based on comments from FOCS-18 reviewers, will merge 2018/326 with 2018/065 and resubmit updates through that other article.

Available format(s)
-- withdrawn --
Cryptographic protocols
Publication info
Preprint. MINOR revision.
zero-knowledgeMIPNEXPmulti-prover interactive proofsnon-locality
Contact author(s)
nan yang @ me com
2018-07-10: withdrawn
2018-04-09: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.