Efficient Batch Verification for UP

Omer Reingold, Guy N. Rothblum, Ron D. Rothblum

TL;DR

This paper introduces a new proof system called Interactive Witness Verification (IWV) that allows a verifier to check NP statements by querying a raw witness and interacting with a prover. They then use this to achieve efficient batch verification for UP statements (NP statements with unique witnesses), reducing communication complexity from linear in the number of statements to a sub-linear polynomial.

What Problem Does This Paper Address?

Imagine you have a bunch of NP statements, and you want to convince someone (a verifier) that all of them are true. The most straightforward way is to send them the "proofs" (witnesses) for each statement. However, if you have many statements, this can involve a lot of data transfer. The core problem this paper tackles is: can we do better? Specifically, can we design an interactive protocol where a prover can convince a verifier of the correctness of k NP statements with a total communication cost that grows less than linearly with k? This is particularly interesting for "UP" statements, which are NP statements guaranteed to have exactly one witness. The challenge is to achieve this efficiency while ensuring the honest prover can still generate the proof quickly.

Methods

The paper's main contribution is a novel proof system called Interactive Witness Verification (IWV). In an IWV, a verifier doesn't get direct access to the entire witness but instead has oracle access to it and interacts with a powerful, untrusted prover. The goal is for the verifier to check the NP statement using only a sublinear number of queries to the witness and a short interaction with the prover. This is distinct from Probabilistically Checkable Proofs (PCPs) where the verifier receives an encoded version of the witness.

The authors then leverage IWVs to build their efficient batch verification protocol for UP statements. The protocol works iteratively:

  1. IWV for Batch Verification: They first construct an IWV for the batch relation (where the statement is that all k individual statements are true). This IWV allows the verifier to make a limited number of queries to the combined witness and interact with the prover.
  2. Recursive Reduction: The key insight is that if the IWV reveals that a subset of statements might be false, they can recursively apply the batch verification protocol to this smaller subset. This process continues until only a small number of statements remain, which can then be verified directly.
  3. Uniqueness of Witnesses: The UP property (unique witnesses) is crucial. It allows them to handle situations where the IWV suggests a statement might be false by having the prover reveal the relevant parts of the witness, and then checking if these witnesses are indeed correct and satisfy certain conditions derived from the IWV.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Interactive Witness Verification (IWV): This is a new primitive that decouples witness verification from direct access to the entire witness, allowing for sublinear query complexity and interaction. It's a powerful tool for scenarios where direct witness access is impractical or impossible.
  • Trading Query and Communication Complexity: The paper shows that for certain NP relations, you can trade off the number of queries a verifier makes to a witness against the communication complexity of the interactive proof. This is formalized in Theorem 2.
  • Recursive Batch Verification: The core idea for achieving sub-linear communication in k is to recursively reduce the problem. Each step of the recursion handles a subset of statements, and the process continues until the problem is small enough to solve directly.
  • Leveraging UP for Soundness: The uniqueness of witnesses in UP statements is critical for the soundness of the batch verification protocol. It allows the protocol to pinpoint potential issues and ensure that a cheating prover cannot hide false statements.

Key Results

  • Efficient Batch Verification for UP: The paper presents an interactive proof system for verifying k UP statements with a communication complexity of $k^\delta \cdot \text{poly}(m)$, where $\delta > 0$ is an arbitrarily small constant and $m$ is the witness length. This is a significant improvement over the naive approach of sending all witnesses.
  • Constant Rounds: The protocol uses a constant number of interaction rounds.
  • Efficient Prover: The honest prover strategy can be implemented in polynomial time given the witnesses.
  • IWV Construction: The paper constructs IWVs for NP relations verifiable by bounded-space Turing machines or bounded-depth circuits, with query complexity $q$ and communication complexity $O(m^{1+d}/q)$.

Limitations and Future Work

  • UP vs. General NP: The main result is for UP statements. A key open question is whether similar efficient batch verification protocols exist for arbitrary NP statements, ideally with an efficient prover. The authors mention that current techniques don't seem to directly extend via standard NP-to-UP reductions.
  • Communication Complexity: While the communication complexity is sub-linear in k, it's still polynomial in m. The authors pose whether communication can grow only poly-logarithmically with k, which might require more rounds.
  • Lower Bounds: The paper provides a lower bound for IWVs, showing that Theorem 9 (which constructs IWVs) is quantitatively almost tight. This lower bound relies on the existence of exponentially strong cryptographic pseudorandom generators.
  • Dataset: No datasets were used or introduced in this theoretical work.

Summary updated

Abstract

Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by simply having the prover send the k NP witnesses, but this involves a lot of communication. Can interaction help? In particular, is it possible to construct interactive proofs for this task whose communication grows sub-linearly with k? Our main result is such an interactive proof for verifying the correctness of any k UP statements (i.e., NP statements that have a unique witness). The proof-system uses only a constant number of rounds and the communication complexity is k^delta * poly(m), where delta>0 is an arbitrarily small constant, m is the length of a single witness, and the poly term refers to a fixed polynomial that only depends on the language and not on delta. The (honest) prover strategy can be implemented in polynomial-time given access to the k (unique) witnesses. Our proof leverages "interactive witness verification" (IWV), a new type of proof-system that may be of independent interest. An IWV is a proof-system in which the verifier needs to verify the correctness of an NP statement using: (i) a sublinear number of queries to an alleged NP witness, and (ii) a short interaction with a powerful but untrusted prover. In contrast to the setting of PCPs and Interactive PCPs, here the verifier only has access to the raw NP witness, rather than some encoding thereof.
BibTeX
@inproceedings{reingold2018efficient,
  author = {Omer Reingold and Guy N. Rothblum and Ron D. Rothblum},
  title = {{Efficient Batch Verification for UP}},
  booktitle = {CCC},
  year = {2018},
  url = {https://openreview.net/forum?id=ZzqDLXqJsI},
}
Figure