Zero-Knowledge Proofs of Proximity
© Itay Berman, Ron D. Rothblum and Vinod Vaikuntanathan. Interactive proofs of proximity (IPPs) are interactive proofs in which the verifier runs in time sub-linear in the input length. Since the verifier cannot even read the entire input, following the property testing literature, we only require t...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137815 |
| _version_ | 1811088156394520576 |
|---|---|
| author | Berman, Itay Rothblum, Ron D. Vaikuntananthan, Vinod |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Berman, Itay Rothblum, Ron D. Vaikuntananthan, Vinod |
| author_sort | Berman, Itay |
| collection | MIT |
| description | © Itay Berman, Ron D. Rothblum and Vinod Vaikuntanathan. Interactive proofs of proximity (IPPs) are interactive proofs in which the verifier runs in time sub-linear 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 zero-knowledge proofs of proximity (ZKPP). A ZKPP convinces a sub-linear time verifier that the input is close to the language (similarly to an IPP) while simultaneously guaranteeing a natural zero-knowledge 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 zero-knowledge where we show that the following hold unconditionally (where N denotes the input length): 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 (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 No(1) time verifier. Statistical ZKPPs for some graph-based 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 one-way functions, every language computable either in (logspace uniform) NC or in SC, has a computational ZKPP with a (roughly) 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) time verifier. |
| first_indexed | 2024-09-23T13:57:09Z |
| format | Article |
| id | mit-1721.1/137815 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:57:09Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1378152023-04-10T19:14:12Z Zero-Knowledge Proofs of Proximity Berman, Itay Rothblum, Ron D. Vaikuntananthan, Vinod Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © Itay Berman, Ron D. Rothblum and Vinod Vaikuntanathan. Interactive proofs of proximity (IPPs) are interactive proofs in which the verifier runs in time sub-linear 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 zero-knowledge proofs of proximity (ZKPP). A ZKPP convinces a sub-linear time verifier that the input is close to the language (similarly to an IPP) while simultaneously guaranteeing a natural zero-knowledge 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 zero-knowledge where we show that the following hold unconditionally (where N denotes the input length): 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 (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 No(1) time verifier. Statistical ZKPPs for some graph-based 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 one-way functions, every language computable either in (logspace uniform) NC or in SC, has a computational ZKPP with a (roughly) 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) time verifier. 2021-11-08T20:18:12Z 2021-11-08T20:18:12Z 2018 2019-07-09T17:01:20Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137815 Berman, Itay, Rothblum, Ron D. and Vaikuntananthan, Vinod. 2018. "Zero-Knowledge Proofs of Proximity." en 10.4230/LIPIcs.ITCS.2018.19 Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Berman, Itay Rothblum, Ron D. Vaikuntananthan, Vinod Zero-Knowledge Proofs of Proximity |
| title | Zero-Knowledge Proofs of Proximity |
| title_full | Zero-Knowledge Proofs of Proximity |
| title_fullStr | Zero-Knowledge Proofs of Proximity |
| title_full_unstemmed | Zero-Knowledge Proofs of Proximity |
| title_short | Zero-Knowledge Proofs of Proximity |
| title_sort | zero knowledge proofs of proximity |
| url | https://hdl.handle.net/1721.1/137815 |
| work_keys_str_mv | AT bermanitay zeroknowledgeproofsofproximity AT rothblumrond zeroknowledgeproofsofproximity AT vaikuntananthanvinod zeroknowledgeproofsofproximity |