Abstract

We discuss a foundational issue in multi-prover interactive proofs (MIP) which we call "contamination" by the verifier. We propose a model which accounts for, and controls, verifier contamination, and show that this model does not lose expressive power. A new characterization of zero-knowledge naturally follows. We show the usefulness of this model by constructing a practical MIP for NP where the provers are spatially separated. Finally, we relate our model to the practical problem of e-voting by constructing a functional voter roster based on distributed trust.