License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.77
URN: urn:nbn:de:0030-drops-156736
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15673/
Goldberg, Guy ;
N. Rothblum, Guy
Sample-Based Proofs of Proximity
Abstract
Suppose we have random sampling access to a huge object, such as a graph or a database. Namely, we can observe the values of random locations in the object, say random records in the database or random edges in the graph. We cannot, however, query locations of our choice. Can we verify complex properties of the object using only this restricted sampling access?
In this work, we initiate the study of sample-based proof systems, where the verifier is extremely constrained; Given an input, the verifier can only obtain samples of uniformly random and i.i.d. locations in the input string, together with the values at those locations. The goal is verifying complex properties in sublinear time, using only this restricted access. Following the literature on Property Testing and on Interactive Proofs of Proximity (IPPs), we seek proof systems where the verifier accepts every input that has the property, and with high probability rejects every input that is far from the property.
We study both interactive and non-interactive sample-based proof systems, showing:
- On the positive side, our main result is that rich families of properties / languages have sub-linear sample-based interactive proofs of proximity (SIPPs). We show that every language in NC has a SIPP, where the sample and communication complexities, as well as the verifier’s running time, are Õ(√n), and with polylog(n) communication rounds. We also show that every language that can be computed in polynomial-time and bounded-polynomial space has a SIPP, where the sample and communication complexities of the protocol, as well as the verifier’s running time are roughly √n, and with a constant number of rounds.
This is achieved by constructing a reduction protocol from SIPPs to IPPs. With the aid of an untrusted prover, this reduction enables a restricted, sample-based verifier to simulate an execution of a (query-based) IPP, even though it cannot query the input. Applying the reduction to known query-based IPPs yields SIPPs for the families described above.
- We show that every language with an adequate (query-based) property tester has a 1-round SIPP with constant sample complexity and logarithmic communication complexity. One such language is equality testing, for which we give an explicit and simple SIPP.
- On the negative side, we show that interaction can be essential: we prove that there is no non-interactive sample-based proof of proximity for equality testing.
- Finally, we prove that private coins can dramatically increase the power of SIPPs. We show a strong separation between the power of public-coin SIPPs and private-coin SIPPs for Equality Testing.
BibTeX - Entry
@InProceedings{goldberg_et_al:LIPIcs.ITCS.2022.77,
author = {Goldberg, Guy and N. Rothblum, Guy},
title = {{Sample-Based Proofs of Proximity}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {77:1--77:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15673},
URN = {urn:nbn:de:0030-drops-156736},
doi = {10.4230/LIPIcs.ITCS.2022.77},
annote = {Keywords: Interactive Proof Systems, Sample-Based Access, Proofs of Proximity}
}
|
Keywords: |
|
Interactive Proof Systems, Sample-Based Access, Proofs of Proximity |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
