Multi-Prover Interactive Proof Systems with Leakage
Abstract
It is known that there exist multi-prover interactive protocols (MIP protocols) for the complexity class NEXP, succinct MIP protocols for NP and multi-prover interactive protocols with shared entanglement (MIP∗ protocols) for RE. This extraordinary power of multi-prover interactive proof systems comes from the assumption that provers do not communicate with each other during the protocols. If they are allowed to communicate freely, the setting is the same as in the single-prover case, and the computational power of the system becomes significantly weaker. In this paper, we investigate for the first time the setting where communication (i.e., leakage of information) between provers is allowed but bounded. We introduce two techniques to approach this question and show that multi-prover interactive proof systems are robust against some amount of leakage. Our first technique is based on parallel repetition theorems. We apply it to show that for any polynomial p, we can construct two-prover one-round MIP and MIP∗ protocols for NEXP and RE, respectively, that are robust against p(n) bits of leakage. We further derive our second technique to convert any low-soundness PCP construction to a two-prover one-round MIP protocol for NP robust against leakage. We also discuss the relation between robustness against leakage in multi-prover interactive proof systems and the Sliding Scale Conjecture in the PCP literature.
Versions
Related
- On quantum interactive proofs with a laconic prover
- Teleportation Game: Quantum Teleportation in Multi-Agent Systems for Interactive Music
- Time-Integrated Leakage as a Dynamical Benchmark for Multi-Mode Superconducting-Qubit Reset
- Proof of the Wave Function Identity, a New Symmetry Constraint for the Three-Electron Quantum Dot in a Magnetic Field and Ad Hoc Generalization to Bound Many-Electron Systems
- Achieving perfect completeness for one- and two-message quantum proof systems
BibTeX
@misc{asadi2026multiprover,
title = {{Multi-Prover Interactive Proof Systems with Leakage}},
author = {Vahid R. Asadi and Atsuya Hasegawa and François Le Gall},
howpublished = {arXiv},
year = {2026},
month = jul,
doi = {10.48550/arxiv.2605.09872},
eprint = {2605.09872},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.09872},
}
RIS
TY - UNPB
TI - Multi-Prover Interactive Proof Systems with Leakage
AU - Vahid R. Asadi
AU - Atsuya Hasegawa
AU - François Le Gall
PY - 2026
DA - 2026/07/05
PB - arXiv
DO - 10.48550/arxiv.2605.09872
UR - https://arxiv.org/abs/2605.09872
AB - It is known that there exist multi-prover interactive protocols (MIP protocols) for the complexity class NEXP, succinct MIP protocols for NP and multi-prover interactive protocols with shared entanglement (MIP^∗ protocols) for RE. This extraordinary power of multi-prover interactive proof systems comes from the assumption that provers do not communicate with each other during the protocols. If they are allowed to communicate freely, the setting is the same as in the single-prover case, and the computational power of the system becomes significantly weaker. In this paper, we investigate for the first time the setting where communication (i.e., leakage of information) between provers is allowed but bounded. We introduce two techniques to approach this question and show that multi-prover interactive proof systems are robust against some amount of leakage. Our first technique is based on parallel repetition theorems. We apply it to show that for any polynomial p, we can construct two-prover one-round MIP and MIP^∗ protocols for NEXP and RE, respectively, that are robust against p(n) bits of leakage. We further derive our second technique to convert any low-soundness PCP construction to a two-prover one-round MIP protocol for NP robust against leakage. We also discuss the relation between robustness against leakage in multi-prover interactive proof systems and the Sliding Scale Conjecture in the PCP literature.
ER -