Itay Berman: Zero-Knowledge Proofs of Proximity

Speaker: Itay Berman, MIT

Date: Friday, March 17, 2017

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: Hewlett, G882

Event Type:

Room Description:

Host: Vinod Vaikuntanathan

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: TALK: Itay Berman: Zero-Knowledge Proofs of Proximity

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 an SZKPP 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:
- Assuming the existence of one-way functions, every language computable either in (logspace uniform) NC or in SC, has a computational zero-knowledge proof of proximity with a (roughly) sqrt(N) time verifier.
- 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.

Joinj work with Ron D. Rothblum and Vinod Vaikuntanathan.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Seminar (CIS) 2017.

Created by Deborah Goodwin at Wednesday, February 15, 2017 at 11:13 AM.