Cryptology ePrint Archive: Report 2018/065

New Perspectives on Multi-Prover Interactive Proofs

Claude Crépeau and Nan Yang

Abstract: In this work, we introduce the \emph{locality hierarchy} for multiparty (multi-round) interaction, and for the first time a complete definition of multi-round multiparty no-signalling distributions and strategies. Within this framework, we define the \emph{locality} of a protocol which involves the provers, verifiers, simulators and distinguishers. We show that the existing protocol (Babai et al., Computational Complexity, Dec 92) for \mathbf{NEXP} and a new zero-knowledge variant are sound in a local sense, and are zero-knowledge in a sense that is even stronger than usually understood.

Finally, we present similar constructions for entangled and no-signalling prover sets for \mathbf{NEXP} and \mathbf{EXP} based on (Ito et al., FOCS'12) and (Kalai et al., STOC'14) using new multi-prover commitment schemes.

Category / Keywords: Multiprover Interactive Proofs

Date: received 14 Jan 2018, last revised 12 Feb 2018

Contact author: crepeau at cs mcgill ca

Available format(s): PDF | BibTeX Citation

Note: Updated certain claims based on STOC-2018 reviewer's reports. To be submitted elsewhere in near future. This paper is a follow-up of .

Version: 20180212:215118 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]