Cryptology ePrint Archive: Report 2018/326

Verifier Non-Locality in Interactive Proofs

Claude Crepeau and Nan Yang

Abstract: 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".

Category / Keywords: cryptographic protocols / zero-knowledge, MIP, NEXP, multi-prover interactive proofs, non-locality

Date: received 7 Apr 2018, withdrawn 10 Jul 2018

Contact author: nan yang at me com

Available format(s): (-- withdrawn --)

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

Version: 20180710:154428 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]