Abstract

Single-prover interactive proofs can recognize PSPACE; if certain complexity assumptions are made, they can do so in zero-knowledge. Generalizing to multiple non-communicating provers extends this class to NEXP, and at the same time removes the complexity assumption needed for zero-knowledge.

However, it was recently discovered that the non-communication condition might be insufficient to guarantee soundness. The provers can form joint randomness through non-local computation without communicating. This could break protocols that rely on the statistical independence of the provers.

In this work, we analyze multi-prover interactive proofs under the constraint of statistical isolation which prohibits non-local computation. We show that there exists perfect zero-knowledge proofs for NEXP under statistical isolation.