ZK-PCPs from Leakage-Resilient Secret Sharing

Abstract

Zero-Knowledge PCPs (ZK-PCPs; Kilian, Petrank, and Tardos, STOC 97) are PCPs with the additional zero-knowledge guarantee that the view of any (possibly malicious) verifier making a bounded number of queries to the proof can be efficiently simulated up to a small statistical distance. Similarly, ZK-PCPs of Proximity (ZK-PCPPs; Ishai and Weiss, TCC 14) are PCPPs in which the view of an adversarial verifier can be efficiently simulated with few queries to the input. Previous ZK-PCP constructions obtained an exponential gap between the query complexity $q$ of the honest verifier, and the bound $q^*$ on the queries of a malicious verifier (i.e., $q=polylog(q^*)$), but required either exponential-time simulation, or adaptive honest verification. This should be contrasted with standard PCPs, that can be verified non-adaptively (i.e., with a single round of queries to the proof). The problem of constructing such ZK-PCPs, even when $q^*=q$, has remained open since they were first introduced more than 2 decades ago. This question is also open for ZK-PCPPs, for which no construction with non-adaptive honest verification is known (not even with exponential-time simulation). We resolve this question by constructing the first ZK-PCPs and ZK-PCPPs which simultaneously achieve efficient zero-knowledge simulation and non-adaptive honest verification. Our schemes have a square-root query gap, namely $q^*/q=O(sqrt(n))$ where $n$ is the input length. Our constructions combine the "MPC-in-the-head" technique (Ishai et al., STOC 07) with leakage-resilient secret sharing. Specifically, we use the MPC-in-the-head technique to construct a ZK-PCP variant over a large alphabet, then employ leakage-resilient secret sharing to design a new alphabet reduction for ZK-PCPs which preserves zero-knowledge.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. ITC 2021
Keywords
Zero Knowledge Probabilistically Checkable Proofs PCPs of Proximity Leakage Resilience Secret Sharing
Contact author(s)
mor weiss @ biu ac il
History
2022-07-15: revised
See all versions
Short URL
https://ia.cr/2021/606

CC BY

BibTeX

@misc{cryptoeprint:2021/606,
author = {Carmit Hazay and Muthuramakrishnan Venkitasubramaniam and Mor Weiss},
title = {ZK-PCPs from Leakage-Resilient Secret Sharing},
howpublished = {Cryptology ePrint Archive, Paper 2021/606},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/606}},
url = {https://eprint.iacr.org/2021/606}
}
`
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.