## Efficient Batch Verification for UP

by Omer Reingold, Guy Rothblum, and Ron Rothblum

#### Oded's comments

In their prior seminal paper,
the authors have introduced the problem of doubly-efficient
batch verification, where the task is to verify $k$ NP-assertions
each having a (unique) NP-witness of length $m$,
and resolved in in complexity $o(km)$, provided $k >> m$;
specifically, for every $\delta>0$, they presented
a constant-round doubly-efficient interactive proof of communication
complexity $k^{\delta}\cdot\poly(m)+k\cdot\poly(\log m)$.
The current paper gets rid of the $k\cdot\poly(\log m)$ term,
yielding communication complexity that is sublinear in $k$.

Note that the celebrated interactive proof system for PSPACE
implies an even lower dependence on the number of statements,
but this comes at the cost of utilizing a non-efficient prover strategy.

#### The original 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 \cdot\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.

See ECCC TR18-022.

Back to
list of Oded's choices.