Paper 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.

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 https://eprint.iacr.org/2017/229 .