arxiv: 2605.09872 · v1 · submitted 2026-05-11 · 🪐 quant-ph · cs.CC

Recognition: no theorem link

Multi-Prover Interactive Proof Systems with Leakage

Atsuya Hasegawa, Fran\c{c}ois Le Gall, Vahid R. Asadi

Authors on Pith no claims yet

Pith reviewed 2026-05-12 05:05 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC

keywords multi-prover interactive proofsMIPMIP*leakageNEXPREparallel repetitionPCP

0 comments

The pith

Two-prover interactive proof systems can verify NEXP and RE even when the provers leak polynomially many bits to each other.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines multi-prover interactive proof systems where provers may exchange bounded information. It proves that for any polynomial p, two-prover one-round MIP protocols for NEXP and MIP* protocols for RE can be made robust to p(n) bits of leakage. This is done using adapted parallel repetition theorems and transformations from low-soundness PCPs. The authors also relate their results to the Sliding Scale Conjecture.

Core claim

For any polynomial p, two-prover one-round MIP protocols for NEXP and MIP* protocols for RE exist that remain sound against p(n) bits of leakage between the provers. A second technique converts low-soundness PCPs into leakage-robust two-prover MIP protocols for NP. The work explores connections to the Sliding Scale Conjecture.

What carries the argument

Parallel repetition theorems extended to settings with bounded leakage between provers.

If this is right

MIP protocols verify NEXP problems even with limited prover communication.
MIP* protocols verify RE with shared entanglement and leakage.
Low-soundness PCPs yield leakage-robust MIP protocols for NP.
Leakage robustness in these systems connects to the Sliding Scale Conjecture.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Practical multi-prover systems might work with imperfect isolation if leakage is small.
New PCP constructions could incorporate leakage tolerance directly.
This model bridges ideal proof systems and real-world noisy communication between parties.

Load-bearing premise

Existing parallel-repetition theorems remain valid when provers exchange polynomially many bits of information during the repetitions.

What would settle it

A proof that parallel repetition loses its soundness guarantee as soon as provers exchange even one bit per round.

read the original abstract

It is known that there exist multi-prover interactive protocols ($\mathsf{MIP}$ protocols) for the complexity class $\mathsf{NEXP}$, succinct $\mathsf{MIP}$ protocols for $\mathsf{NP}$ and multi-prover interactive protocols with shared entanglement ($\mathsf{MIP}^\ast$ protocols) for $\mathsf{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 $\mathsf{MIP}$ and $\mathsf{MIP}^\ast$ protocols for $\mathsf{NEXP}$ and $\mathsf{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 $\mathsf{MIP}$ protocol for $\mathsf{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives the first explicit constructions of two-prover MIP protocols for NEXP and MIP* protocols for RE that stay sound under any polynomial bits of leakage between provers.

read the letter

The main takeaway is that MIP and MIP* protocols remain powerful even when the provers are allowed to exchange a polynomial number of bits. The authors adapt parallel repetition to produce one-round two-prover protocols for NEXP and RE that tolerate p(n) leakage, and they add a separate PCP-to-MIP conversion that yields leakage-robust protocols for NP. They also note a link to the sliding scale conjecture, which helps place the leakage parameter in context with existing soundness trade-offs. This is the first systematic look at bounded leakage in the multi-prover setting, and the constructions are presented as straightforward applications of known tools rather than entirely new machinery. The positive results are useful because they show the model does not collapse right away once perfect isolation is relaxed. The parallel-repetition argument is the part that needs the closest check. Classical theorems rely on independent answer distributions across repetitions, and leakage introduces a channel that can correlate the provers' views. If the paper only invokes the standard theorems without an extra bound on how the p(n) bits affect the error decay, the claimed soundness for arbitrary polynomials would rest on an unverified step. The abstract states the constructions work, so presumably they supply the adjustment, but that is the section a referee should verify first. The work is aimed at people who study interactive proofs, PCPs, and quantum complexity. A reader who wants to see how these systems behave under imperfect isolation will find concrete constructions and open directions worth following. It deserves a serious referee because it opens a natural model with explicit positive results, even if the leakage analysis requires tightening.

Referee Report

2 major / 2 minor

Summary. The paper investigates multi-prover interactive proofs (MIP and MIP*) under bounded leakage between provers. It claims that, for any polynomial p, there exist two-prover one-round MIP protocols for NEXP and MIP* protocols for RE that remain sound even when the provers may exchange p(n) bits of information. The constructions rely on applying parallel-repetition theorems to base protocols and on converting low-soundness PCPs into leakage-robust MIPs for NP; the work also relates leakage robustness to the Sliding Scale Conjecture.

Significance. If the soundness claims hold, the results demonstrate that the extraordinary power of MIP and MIP* is robust to polynomially bounded communication between provers, thereby extending classical results on interactive proofs to a more realistic leakage model. The explicit constructions via parallel repetition and the PCP conversion technique, together with the connection to the Sliding Scale Conjecture, would constitute a meaningful contribution to the study of interactive proofs under relaxed independence assumptions.

major comments (2)

[Parallel-repetition technique (application to MIP/MIP*)] The central claim for NEXP and RE (abstract and the parallel-repetition section) rests on invoking standard parallel-repetition theorems (Raz, Holenstein, etc.) after allowing p(n)-bit leakage. These theorems derive exponential soundness decay from the assumption that answer distributions remain independent across repetitions. The manuscript must supply an explicit argument showing that the p(n)-bit channel does not prevent the error from falling below the required threshold (1/poly or exponentially small); without a modified analysis or an additive error bound accounting for the leakage, the soundness guarantee is unsupported.
[PCP conversion technique] The PCP-to-MIP conversion for NP (second technique) is described at a high level. The manuscript should state the precise soundness error of the starting PCP, the exact leakage model (whether leakage occurs before or after the PCP queries are answered), and the resulting soundness of the two-prover protocol after conversion.

minor comments (2)

[Introduction / Model] Notation for the leakage model (e.g., whether the p(n) bits are exchanged once or per round) should be defined formally in a dedicated subsection before the constructions.
[Relation to Sliding Scale Conjecture] The discussion of the Sliding Scale Conjecture would benefit from a short paragraph clarifying whether the new leakage-robust protocols yield any quantitative improvement or merely a qualitative analogy.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable suggestions. We address the two major comments point by point below. Both points identify areas where the manuscript would benefit from additional detail and explicit arguments; we will revise the paper to incorporate these clarifications and supporting analyses.

read point-by-point responses

Referee: The central claim for NEXP and RE (abstract and the parallel-repetition section) rests on invoking standard parallel-repetition theorems (Raz, Holenstein, etc.) after allowing p(n)-bit leakage. These theorems derive exponential soundness decay from the assumption that answer distributions remain independent across repetitions. The manuscript must supply an explicit argument showing that the p(n)-bit channel does not prevent the error from falling below the required threshold (1/poly or exponentially small); without a modified analysis or an additive error bound accounting for the leakage, the soundness guarantee is unsupported.

Authors: We agree that a direct invocation of standard parallel-repetition theorems requires justification when a bounded leakage channel is present, as the theorems rely on independence of the provers' answers. In the revised manuscript we will add an explicit analysis in the parallel-repetition section. Specifically, we will show that p(n) bits of leakage between the two provers can be modeled as an additive perturbation to the joint answer distribution; this perturbation increases the soundness error by at most an additive term of O(p(n)·2^{-Ω(r)}) where r denotes the number of repetitions. By choosing r sufficiently large (still polynomial for the NEXP case and appropriate for the MIP* case), the overall soundness error can be driven below any 1/poly(n) or exponentially small threshold required by the target classes. This bound follows from a straightforward hybrid argument that accounts for the mutual information introduced by the leakage channel while preserving the exponential decay rate of the underlying repetition theorem. revision: yes
Referee: The PCP-to-MIP conversion for NP (second technique) is described at a high level. The manuscript should state the precise soundness error of the starting PCP, the exact leakage model (whether leakage occurs before or after the PCP queries are answered), and the resulting soundness of the two-prover protocol after conversion.

Authors: We accept that the current description of the PCP-to-MIP conversion is too high-level. In the revision we will make the following precise statements: (i) the starting PCP for NP has soundness error at most 1−1/poly(n) (as obtained from standard low-soundness PCP constructions); (ii) the leakage model is that the two provers may exchange up to p(n) bits of information after receiving their respective PCP queries but before producing their answers; (iii) the resulting two-prover one-round MIP protocol for NP has soundness error at most s + O(p(n)/ℓ) where s is the PCP soundness error and ℓ is the query length (the precise additive term arises from the information leaked about the PCP answers). We will also include a short proof sketch of the conversion that makes these parameters explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results apply external theorems without reduction to inputs

full rationale

The paper's central constructions for leakage-robust MIP and MIP* protocols are explicitly described as applications of existing parallel-repetition theorems and conversions from low-soundness PCPs. No equations, definitions, or steps reduce the claimed robustness (against p(n) leakage) to a fitted parameter, self-defined quantity, or prior result by the same authors. The derivation chain relies on external benchmarks (Raz/Holenstein-style theorems and PCP literature) whose assumptions are stated separately from the target result. Any self-citations present are not load-bearing for the main claims.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the validity of parallel-repetition theorems for MIP/MIP* under a leakage model and on the existence of low-soundness PCPs; no new free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption Parallel repetition theorems hold for MIP and MIP* protocols even when provers exchange a polynomial number of bits.
Invoked to obtain leakage-robust protocols for NEXP and RE.
domain assumption Low-soundness PCP constructions exist and can be converted into two-prover one-round MIP protocols.
Used for the NP leakage-robust protocol.

pith-pipeline@v0.9.0 · 5591 in / 1314 out tokens · 41369 ms · 2026-05-12T05:05:00.675008+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · 1 internal anchor

[1]

A simple demonstration of Bell’s theorem involving two observers and no probabilities or inequalities.arXiv preprint quant-ph/0206070,

[Ara02] Padmanabhan K Aravind. A simple demonstration of Bell’s theorem involving two observers and no probabilities or inequalities.arXiv preprint quant-ph/0206070,

work page arXiv
[2]

Efficient Probabilistically Checkable Proofs and Applications to Approximations

[BGLR93] Mihir Bellare, Shafi Goldwasser, Carsten Lund, and Alexander Russell. Efficient Probabilistically Checkable Proofs and Applications to Approximations. InProceed- ings of the 25th annual ACM symposium on Theory of computing (STOC 1993), pages 294–304,

work page 1993
[3]

Quasi-linear size PCPs with small soundness from HDX

21 [BMVY25] Mitali Bafna, Dor Minzer, Nikhil Vyas, and Zhiwei Yun. Quasi-linear size PCPs with small soundness from HDX. InProceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), pages 45–53,

work page 2025
[4]

Gap amplification fails below 1/2.Comment on ECCC TR05-046, can be found at http://eccc

[Bog05] Andrej Bogdanov. Gap amplification fails below 1/2.Comment on ECCC TR05-046, can be found at http://eccc. uni-trier. de/eccc-reports/2005/TR05-046/commt01. pdf,

work page 2005
[5]

Multi-prover interactive proofs: how to remove intractability assumptions

[BOGKW88] Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson. Multi-prover interactive proofs: how to remove intractability assumptions. InProceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC 1988), page 113–131,

work page 1988
[6]

Quantum FHE (almost) as secure as classical

[Bra18] Zvika Brakerski. Quantum FHE (almost) as secure as classical. InProceedings of the Annual International Cryptology Conference (CRYPTO 2018), pages 67–95. Springer,

work page 2018
[7]

Direct products in communication complexity

[BRWY13] Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff. Direct products in communication complexity. InProceedings of 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS 2013), pages 746–755,

work page 2013
[8]

Consequences and limits of nonlocal strategies

[CHTW04] Richard Cleve, Peter Hoyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. InProceedings of 19th IEEE Annual Conference on Computational Complexity (CCC 2004), pages 236–249,

work page 2004
[9]

Informational complexity and the direct sum problem for simultaneous message complexity

[CSWY01] Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew Yao. Informational complexity and the direct sum problem for simultaneous message complexity. In Proceedings of 42nd IEEE Symposium on Foundations of Computer Science (FOCS 2001), pages 270–278,

work page 2001
[10]

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

[DHK15] Irit Dinur, Prahladh Harsha, and Guy Kindler. Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition. InProceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), page 267–276,

work page 2015
[11]

Quantum computing: L ecture notes

[dW19] Ronald de Wolf. Quantum computing: Lecture notes.arXiv preprint arXiv:1907.09415,

work page arXiv 1907
[12]

Private coins versus public coins in interactive proof systems

[GS86] Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. InProceedings of the 18th annual ACM symposium on Theory of computing (STOC 1986), pages 59–68,

work page 1986
[13]

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement

[HLGM25] Atsuya Hasegawa, Fran¸ cois Le Gall, and Augusto Modanese. Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement. arXiv preprint arXiv:2505.16457,

work page internal anchor Pith review Pith/arXiv arXiv
[14]

A multi-prover interactive proof for NEXP sound against entangled provers

[IV12] Tsuyoshi Ito and Thomas Vidick. A multi-prover interactive proof for NEXP sound against entangled provers. InProceedings of 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012), pages 243–252,

work page 2012
[15]

MIP*= RE.arXiv preprint arXiv:2001.04383,

[JNV+20] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*= RE.arXiv preprint arXiv:2001.04383,

work page arXiv 2001
[16]

A parallel repetition theorem for entangled two-player one-round games under product distributions

[JPY14] Rahul Jain, Attila Pereszl´ enyi, and Penghui Yao. A parallel repetition theorem for entangled two-player one-round games under product distributions. InProceedings of 2014 IEEE 29th Conference on Computational Complexity (CCC 2014), pages 209–216,

work page 2014
[17]

Prior entanglement, message compression and privacy in quantum communication

[JRS05] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. Prior entanglement, message compression and privacy in quantum communication. InProceedings of 20th Annual IEEE Conference on Computational Complexity (CCC 2005), pages 285–296,

work page 2005
[18]

Quantum advan- tage from any non-local game

[KLVY23] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum advan- tage from any non-local game. InProceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pages 1617–1628,

work page 2023
[19]

A bound on the quantum value of all compiled nonlocal games

23 [KMP+25] Alexander Kulpe, Giulio Malavolta, Connor Paddock, Simon Schmidt, and Michael Walter. A bound on the quantum value of all compiled nonlocal games. InProceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), pages 222–233,

work page 2025
[20]

Parallel repetition of entangled games

[KV11] Julia Kempe and Thomas Vidick. Parallel repetition of entangled games. InPro- ceedings of the 43rd annual ACM symposium on Theory of computing (STOC 2011), pages 353–362,

work page 2011
[21]

Two prover perfect zero knowledge for MIP*

[MS24] Kieran Mastel and William Slofstra. Two prover perfect zero knowledge for MIP*. InProceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), pages 991–1002,

work page 2024
[22]

NEEXP is contained in MIP*

[NW19] Anand Natarajan and John Wright. NEEXP is contained in MIP*. InProceedings of 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), pages 510–518,

work page 2019
[23]

Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification

[NZ23a] Anand Natarajan and Tina Zhang. Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification. InProceedings of 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS 2023), pages 1342–1348,

work page 2023
[24]

Quantum free games

[NZ23b] Anand Natarajan and Tina Zhang. Quantum free games. InProceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pages 1603–1616,

work page 2023
[25]

A Parallel Repetition Theorem for All Entangled Games

[Yue16] Henry Yuen. A Parallel Repetition Theorem for All Entangled Games. InProceed- ings of 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 ofLIPIcs, pages 77:1–77:13,

work page 2016