Abstract
Interactive proofs of proximity (IPPs) are interactive proofs in which the verifier runs in time sublinear in the input length. Since the verifier cannot even read the entire input, following the property testing literature, we only require that the verifier reject inputs that are far from the language (and, as usual, accept inputs that are in the language).
In this work, we initiate the study of zeroknowledge proofs of proximity (ZKPP). A ZKPP convinces a sublinear time verifier that the input is close to the language (similarly to an IPP) while simultaneously guaranteeing a natural zeroknowledge property. Specifically, the verifier learns nothing beyond (1) the fact that the input is in the language, and (2) what it could additionally infer by reading a few bits of the input.
Our main focus is the setting of statistical zeroknowledge where we show that the following hold unconditionally (where N denotes the input length):
 Statistical ZKPPs can be subexponentially more efficient than property testers (or even noninteractive IPPs): We show a natural property which has a statistical ZKPP with a polylog(N) time verifier, but requires Omega(sqrt(N)) queries (and hence also runtime) for every property tester.
 Statistical ZKPPs can be subexponentially less efficient than IPPs: We show a property which has an IPP with a polylog(N) time verifier, but cannot have a statistical ZKPP with even an N^(o(1)) time verifier.
 Statistical ZKPPs for some graphbased properties such as promise versions of expansion and bipartiteness, in the bounded degree graph model, with polylog(N) time verifiers exist.
Lastly, we also consider the computational setting where we show that:
 Assuming the existence of oneway functions, every language computable either in (logspace uniform) NC or in SC, has a computational ZKPP with a (roughly) sqrt(N) time verifier.
 Assuming the existence of collisionresistant hash functions, every language in NP has a statistical zeroknowledge argument of proximity with a polylog(N) time verifier.
BibTeX  Entry
@InProceedings{berman_et_al:LIPIcs:2018:8357,
author = {Itay Berman and Ron D. Rothblum and Vinod Vaikuntanathan},
title = {{ZeroKnowledge Proofs of Proximity}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {19:119:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770606},
ISSN = {18688969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8357},
URN = {urn:nbn:de:0030drops83575},
doi = {10.4230/LIPIcs.ITCS.2018.19},
annote = {Keywords: Property Testing, Interactive Proofs, ZeroKnowledge}
}
Keywords: 

Property Testing, Interactive Proofs, ZeroKnowledge 
Collection: 

9th Innovations in Theoretical Computer Science Conference (ITCS 2018) 
Issue Date: 

2018 
Date of publication: 

12.01.2018 