Paper 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".
Note: Based on comments from FOCS-18 reviewers, will merge 2018/326 with 2018/065 and resubmit updates through that other article.
Metadata
- Available format(s)
- -- withdrawn --
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- zero-knowledgeMIPNEXPmulti-prover interactive proofsnon-locality
- Contact author(s)
- nan yang @ me com
- History
- 2018-07-10: withdrawn
- 2018-04-09: received
- See all versions
- Short URL
- https://ia.cr/2018/326
- License
-
CC BY