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 sublinearly 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 proofsystem 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 polynomialtime given access to the k (unique) witnesses.
Our proof leverages "interactive witness verification" (IWV), a new type of proofsystem that may be of independent interest. An IWV is a proofsystem 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  Entry
@InProceedings{reingold_et_al:LIPIcs:2018:8868,
author = {Omer Reingold and Guy N. Rothblum and Ron D. Rothblum},
title = {{Efficient Batch Verification for UP}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {22:122:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8868},
URN = {urn:nbn:de:0030drops88681},
doi = {10.4230/LIPIcs.CCC.2018.22},
annote = {Keywords: Interactive Proof, Batch Verification, Unique Solution}
}
Keywords: 

Interactive Proof, Batch Verification, Unique Solution 
Collection: 

33rd Computational Complexity Conference (CCC 2018) 
Issue Date: 

2018 
Date of publication: 

04.06.2018 