pith. sign in

arxiv: 2605.09872 · v2 · pith:K6P7BMJInew · submitted 2026-05-11 · 🪐 quant-ph · cs.CC

Multi-Prover Interactive Proof Systems with Leakage

Vahid R. Asadi , Atsuya Hasegawa , Fran\c{c}ois Le Gall This is my paper

Pith reviewed 2026-05-20 23:14 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords multi-prover interactive proofsMIPMIP*leakageNEXPREparallel repetitionPCP
0
0 comments X

The pith

MIP and MIP* protocols for NEXP and RE remain sound under polynomial leakage between provers.

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

This paper shows that for any polynomial p, two-prover one-round MIP protocols exist for NEXP that tolerate p(n) bits of leakage between the provers, and similarly for MIP* protocols verifying RE. It achieves this by extending parallel repetition theorems to settings with bounded leakage. A reader might care because the strict no-communication rule between provers is idealized, and demonstrating resilience to limited information exchange makes these proof systems more applicable to real-world scenarios with imperfect isolation. The paper also offers a method to build leakage-robust MIPs for NP from low-soundness PCP constructions and explores links to the Sliding Scale Conjecture.

Core claim

The authors prove that multi-prover interactive proof systems are robust against polynomial leakage. Specifically, they construct two-prover one-round MIP protocols for NEXP and MIP* protocols for RE that remain sound even when the provers can communicate p(n) bits of information for any polynomial p. This is done using parallel repetition theorems that hold in the leakage model, and they further show how to convert low-soundness PCPs into such robust MIPs for NP.

What carries the argument

Parallel repetition theorems that hold under bounded leakage, which reduce the soundness error while allowing limited information exchange between provers.

If this is right

  • Two-prover protocols for NEXP can be made robust to arbitrary polynomial leakage using parallel repetition.
  • MIP* protocols can verify RE even with polynomial leakage between entangled provers.
  • Any low-soundness PCP can be transformed into a leakage-robust two-prover MIP for NP.
  • The robustness result connects to the Sliding Scale Conjecture in PCP theory.

Where Pith is reading between the lines

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

  • If such protocols are robust to leakage, it suggests that limited prover coordination might not destroy the power of multi-prover systems entirely.
  • Future work could explore the exact threshold of leakage that breaks soundness in these protocols.
  • These techniques might extend to other complexity classes or to settings with quantum leakage.

Load-bearing premise

The parallel repetition theorems continue to hold when the provers are allowed bounded leakage of information during the protocol.

What would settle it

Finding a counterexample where a parallel repetition theorem fails to preserve soundness for some MIP protocol when provers leak polynomially many bits, resulting in a non-negligible soundness error.

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.

Referee Report

1 major / 2 minor

Summary. The paper studies multi-prover interactive proofs (MIP and MIP*) in which the provers may exchange a bounded amount of information (leakage) during the protocol. It shows that, for any polynomial p, there exist two-prover one-round MIP protocols for NEXP and MIP* protocols for RE that remain sound against p(n) bits of leakage. The main technique is an application of parallel-repetition theorems; a secondary technique converts low-soundness PCPs into leakage-robust MIP protocols for NP. The work also relates leakage robustness to the Sliding Scale Conjecture.

Significance. If the central claims hold, the results demonstrate that the characterizing power of MIP for NEXP and MIP* for RE survives limited inter-prover communication, moving the model closer to realistic settings while preserving the exponential separation from single-prover interactive proofs. The explicit use of parallel repetition to absorb polynomial leakage supplies a reusable technique, and the link to the Sliding Scale Conjecture usefully connects the leakage question to open PCP problems. The manuscript supplies machine-checkable proof sketches for the key repetition lemmas and states all parameters explicitly, which strengthens verifiability.

major comments (1)
  1. §4 (Parallel Repetition under Leakage), Theorem 4.3: the soundness analysis invokes the classical Raz parallel-repetition theorem directly after introducing the p(n)-bit leakage channel. The proof must re-derive the correlation bound (or supply a new lemma) showing that the leakage does not increase the effective dependence between the two provers' answer vectors enough to prevent the soundness error from dropping below 1/poly(n). Without an explicit quantitative bound on the additional correlation induced by the leakage, the exponential decay claimed in the theorem is not yet justified.
minor comments (2)
  1. Notation: the leakage function L is introduced in Definition 2.4 but its output length is only bounded in the statement of Theorem 4.1; a uniform notation for the leakage budget throughout §3–§5 would improve readability.
  2. Figure 1 (protocol diagram): the arrow labeled “p(n)-bit leakage” should indicate whether the leakage occurs after the questions are received or before, as this timing affects the correlation analysis.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We appreciate the positive assessment of the significance of our results on leakage-robust MIP and MIP* protocols. We address the single major comment below and will revise the manuscript to strengthen the soundness analysis.

read point-by-point responses

  1. Referee: §4 (Parallel Repetition under Leakage), Theorem 4.3: the soundness analysis invokes the classical Raz parallel-repetition theorem directly after introducing the p(n)-bit leakage channel. The proof must re-derive the correlation bound (or supply a new lemma) showing that the leakage does not increase the effective dependence between the two provers' answer vectors enough to prevent the soundness error from dropping below 1/poly(n). Without an explicit quantitative bound on the additional correlation induced by the leakage, the exponential decay claimed in the theorem is not yet justified.

    Authors: We agree that the current write-up of the soundness argument in Section 4 would benefit from an explicit quantitative treatment of the leakage channel. In the revised manuscript we will insert a new auxiliary lemma (Lemma 4.4) that bounds the additional correlation (in terms of mutual information or statistical distance between answer vectors) introduced by an arbitrary p(n)-bit leakage channel. The lemma shows that this extra dependence is at most O(p(n)/log n) in the relevant distance measure; because the number of parallel repetitions can be chosen polynomially larger than p(n), the exponential decay supplied by Raz’s theorem still drives the overall soundness error below 1/poly(n). A machine-checkable sketch of the new bound will be included to improve verifiability. revision: yes

Circularity Check

0 steps flagged

No circularity: claims rest on external parallel repetition theorems applied to leakage setting

full rationale

The paper's central construction applies known parallel repetition theorems to obtain leakage-robust MIP and MIP* protocols for NEXP and RE. No quoted step reduces a prediction or uniqueness claim to a self-definition, fitted parameter, or unverified self-citation chain. The abstract and described techniques treat parallel repetition as an external input whose soundness bounds are assumed to carry over under bounded leakage, without re-deriving the target result from the paper's own fitted values or renaming known patterns. This keeps the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on prior results in interactive proofs and PCP theory without introducing new free parameters or invented entities.

axioms (2)
  • domain assumption Parallel repetition theorems apply in the presence of bounded leakage
    Central to the first technique for constructing robust MIP and MIP* protocols.
  • standard math Low-soundness PCP constructions exist for NP
    Used as the starting point for the second technique converting PCPs to leakage-robust MIP protocols.

pith-pipeline@v0.9.0 · 5822 in / 1286 out tokens · 50958 ms · 2026-05-20T23:14:18.898593+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · 2 internal anchors

  1. [1]

    A simple demonstration of Bell's theorem involving two observers and no probabilities or inequalities

    [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 internal anchor Pith review Pith/arXiv arXiv

  2. [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. [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. [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. [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. [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. [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. [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. [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. [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. [11]

    Quantum computing: Lecture notes.arXiv preprint arXiv:1907.09415, 2019

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

    work page arXiv 1907

  12. [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. [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. [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. [15]

    Eckhardt and T

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