Batch Verification and Proofs of Proximity with Polylog Overhead

by Guy Rothblum and Ron Rothblum

Oded's comments

Yes, I have written about batch verification a month ago, and yet I'm happy to write about it again, let alone when there are news to report.

The achievement of this work is significantly reducing the dependency of the communication complexity on the number of instances, denoted k. While in prior works the dependency was linear in k or a constant power of k (see RRR16 and RRR18, resp.), the current result is polylogarithmic in k. (Admittingly, the round complexity increases from a constant to polylogarithmic in k.)

Another contribution is to interactive proofs of proximity (IPPs). Here the improvement is in reducing the query-times-communication product from $n^{1+o(1)}$ to $\tildeO(n)$, which is particularly significant at the extremes; specifically, using query complexity $n/\poly(\log n))$, one can get polylogarithmic communication complexity.

The original abstract

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication (without making cryptographic assumptions or bounding the computational power of a malicious Alice)? This is the question of batch verification for NP statements.

Our main result is a new interactive proof protocol for verifying the correctness of k UP statements (NP statements with a unique witness) using communication that is poly-logarithmic in k (and a fixed polynomial in the length of a single witness).

This result is obtained by making progress on a different question in the study of interactive proofs. Suppose Alice wants to convince Bob that a huge dataset has some property. Can this be done if Bob can't even read the entire input? In other words, what properties can be verified in sublinear time? An Interactive Proof of Proximity guarantees that Bob accepts if the input has the property, and rejects if the input is far (say in Hamming distance) from having the property. Two central complexity measures of such a protocol are the query and communication complexities (which should both be sublinear). For every query parameter $q$, and for every language in logspace uniform NC, we construct an interactive proof of proximity with query complexity $q$ and communication complexity $(n/q) \cdot \polylog(n)$.

Both results are optimal up to poly-logarithmic factors, under reasonable complexity-theoretic or cryptographic assumptions. The second result, which is our main technical contribution, builds on a distance amplification technique introduced in a beautiful recent work of Ben-Sasson, Kopparty and Saraf [CCC 2018].

Available from ECCC TR20-157.

Back to list of Oded's choices.