Doubly Sub-Linear Interactive Proofs of Proximity

Noga Amir, Oded Goldreich, Guy N. Rothblum

TL;DR

This paper introduces "doubly-sublinear interactive proofs of proximity" (dsIPPs), a new type of interactive proof system where both the verifier and the honest prover have significantly sub-linear query complexity. This is a crucial step towards making interactive proofs practical for large datasets, as it drastically reduces the computational burden on the prover.

What Problem Does This Paper Address?

Interactive proofs of proximity (IPPs) are a powerful tool for verifying properties of large datasets without requiring the verifier to read the entire input. However, traditional IPPs often require the "honest prover" to have a query complexity that is linear in the input size, making them impractical for massive datasets. This paper addresses this limitation by proposing "doubly-efficient" interactive proofs, specifically focusing on reducing the query complexity of both the verifier and the honest prover to be significantly sub-linear. This is particularly important for properties that can already be tested efficiently (i.e., with sub-linear query complexity), as it aims to bridge the gap between efficient testing and efficient proving.

Methods

The authors introduce the concept of doubly-sublinear IPPs (dsIPPs), which have two key characteristics:

  1. Verifier's query complexity is significantly smaller than the tester's.
  2. Honest prover's query complexity is not much larger than the tester's.

A core technique employed is a recursive divide-and-conquer approach. For a given property and input, the problem is broken down into smaller sub-problems. The honest prover, instead of computing exact values for these sub-problems (which would require reading the entire input), uses distance approximators. These approximators provide estimates of the distance of a sub-problem's input from the desired property, with controlled error. This allows the prover to avoid reading the entire input while still providing sufficient information for the verifier to make a decision with high probability.

The paper constructs dsIPPs for several problems, including:

  • Properties decidable by constant-width read-once oblivious branching programs (ROOBPs).
  • Hamming weight approximation.
  • Permutation testing.
  • A relaxation of graph bipartiteness.

A key insight is that the honest prover often does not employ an "optimal" strategy (one that maximizes the verifier's acceptance probability) because it cannot afford to read the entire input. This leads to a trade-off between the number of rounds and the prover's query complexity.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and algorithms for abstract properties and input types (strings, graphs, functions), rather than specific real-world datasets.

Key Insights and Ideas

  • The "doubly-sublinear" paradigm: This is the central contribution. It redefines "doubly-efficient" in the context of interactive proofs to specifically target sub-linear query complexity for both parties, making IPPs more practical for large-scale applications.
  • Prover's sub-optimal strategy: The realization that the honest prover doesn't need to be optimal (in terms of acceptance probability) to achieve sub-linear query complexity is crucial. This allows for the use of approximations, which are computationally cheaper than exact computations.
  • Recursive decomposition with distance approximation: This is the primary algorithmic technique. Breaking down problems and using approximate answers from sub-problems is a powerful way to reduce the prover's query complexity.
  • Trade-off between rounds and prover complexity: The paper highlights that increasing the number of rounds in the protocol can decrease the honest prover's query complexity, offering flexibility in protocol design.

Key Results

The paper presents several dsIPPs with provable guarantees:

  • ROOBPs: A dsIPP for properties decidable by constant-width ROOBPs where the verifier's query complexity is $O(1/\varepsilon)$ and the honest prover's query complexity is $\tilde{O}(n^{1/r(n)})$, where $r(n)$ is the number of rounds.
  • Hamming Weight: A dsIPP for Hamming weight with $O(1/\varepsilon)$ verifier query complexity and $\tilde{O}(n^{1/r(n)} \cdot r(n)^3/\varepsilon^3)$ honest prover query complexity.
  • Permutation Testing: A 1-round dsIPP with verifier query complexity $O((n/\varepsilon)^{0.5-\alpha})$ and honest prover query complexity $O((n/\varepsilon)^{0.5+\alpha})$ for any $\alpha \in (0, 0.5)$.
  • Bipartiteness: A 1-round dsIPP for rapidly-mixing graphs in the bounded-degree model with $O(\log(n)/\varepsilon)$ verifier query complexity and $\tilde{O}(\sqrt{n}/\varepsilon)$ honest prover query complexity.

Limitations and Future Work

  • Prover's sub-optimal completeness: A direct consequence of the prover not reading the entire input is that the dsIPPs presented do not achieve "perfect completeness" (i.e., the verifier might reject an input that has the property with a small probability).
  • Width dependence for ROOBPs: The dsIPP for ROOBPs has an exponential dependence on the width of the branching program, limiting its applicability to constant-width cases.
  • Future Work: The authors suggest exploring dsIPPs with linear or even polynomial communication complexity, and investigating whether the dependence on the proximity parameter $\varepsilon$ can be improved in certain cases (e.g., from cubic to quadratic for Hamming weight). They also hint at the potential for further research into the trade-offs between rounds, query complexity, and communication complexity.

Summary updated

Abstract

We initiate a study of doubly-efficient interactive proofs of proximity, while focusing on properties that can be tested within query-complexity that is significantly sub-linear, and seeking interactive proofs of proximity in which 1) The query-complexity of verification is significantly smaller than the query-complexity of testing. 2) The query-complexity of the honest prover strategy is not much larger than the query-complexity of testing. We call such proof systems doubly-sublinear IPPs (dsIPPs). We present a few doubly-sublinear IPPs. A salient feature of these IPPs is that the honest prover does not employ an optimal strategy (i.e. a strategy that maximizes the verifier’s acceptance probability). In particular, the honest prover in our IPP for sets recognizable by constant-width read-once oblivious branching programs uses a distance-approximator for such sets.
BibTeX
@inproceedings{amir2025doubly,
  author = {Noga Amir and Oded Goldreich and Guy N. Rothblum},
  title = {{Doubly Sub-Linear Interactive Proofs of Proximity}},
  booktitle = {ITCS},
  year = {2025},
  url = {https://openreview.net/forum?id=EwJ2dlq8gf},
}
Figure