Paper 2017/114

Zero-Knowledge Proofs of Proximity

Itay Berman, Ron D. Rothblum, and Vinod Vaikuntanathan

Abstract

Interactive proofs of proximity (Ergun, Kumar and Rubinfeld, Information & Computation, 2004 and Rothblum, Vadhan and Wigderson, STOC 2013), or IPPs, are interactive proofs in which the verifier runs in time sub-linear in the input's length. Since the verifier cannot even read the entire input, following the property testing literature, the requirement is that she accepts inputs that are in the language and rejects ones that are far from the language. However, these proofs could (and in many cases, do) betray considerable global information about the input to the verifier. In this work, we initiate the study of zero-knowledge proofs of proximity (ZKPP). A ZKPP convinces a sub-linear time verifier while ensuring that she learns nothing more than a few locations of the input (and the fact that the input is ``close'' to the language). Our main focus is the setting of statistical zero-knowledge where we show that the following hold unconditionally (where $N$ denotes the input size): * Statistical ZKPPs can be sub-exponentially more efficient than property testers (or even non-interactive 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 sub-exponentially 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 graph-based properties such as promise versions of expansion and bipartiteness. Lastly, we also consider the computational setting where we show that: 1. Assuming the existence of one-way functions, every language computable either in (logspace uniform) NC or in SC, has a computational ZKPP with a (roughly) $\sqrt{N}$ time verifier. 2. Assuming the existence of collision-resistant hash functions, every language in NP has a statistical zero-knowledge argument of proximity with a polylog(N) verifier.