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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Zero KnowledgeProofs of Proximity
Contact author(s)
ronr @ csail mit edu
History
2017-02-14: received
Short URL
https://ia.cr/2017/114
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/114,
      author = {Itay Berman and Ron D.  Rothblum and Vinod Vaikuntanathan},
      title = {Zero-Knowledge Proofs of Proximity},
      howpublished = {Cryptology ePrint Archive, Paper 2017/114},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/114}},
      url = {https://eprint.iacr.org/2017/114}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.