Cryptology ePrint Archive: Report 2017/114

Zero-Knowledge Proofs of Proximity

Itay Berman and 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.

Category / Keywords: foundations / Zero Knowledge, Proofs of Proximity

Date: received 11 Feb 2017

Contact author: ronr at csail mit edu

Available format(s): PDF | BibTeX Citation

Version: 20170214:183515 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]