License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2021.6
URN: urn:nbn:de:0030-drops-143250
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14325/
Go to the corresponding LIPIcs Volume Portal

Hazay, Carmit ; Venkitasubramaniam, Muthuramakrishnan ; Weiss, Mor

ZK-PCPs from Leakage-Resilient Secret Sharing

pdf-format:
LIPIcs-ITC-2021-6.pdf (0.8 MB)

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 = poly log (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(√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.

BibTeX - Entry

@InProceedings{hazay_et_al:LIPIcs.ITC.2021.6,
  author =	{Hazay, Carmit and Venkitasubramaniam, Muthuramakrishnan and Weiss, Mor},
  title =	{{ZK-PCPs from Leakage-Resilient Secret Sharing}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{6:1--6:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14325},
  URN =		{urn:nbn:de:0030-drops-143250},
  doi =		{10.4230/LIPIcs.ITC.2021.6},
  annote =	{Keywords: Zero Knowledge, Probabilisitically Checkable Proofs, PCPs of Proximity, Leakage Resilience, Secret Sharing}
}

Keywords: Zero Knowledge, Probabilisitically Checkable Proofs, PCPs of Proximity, Leakage Resilience, Secret Sharing
Collection: 2nd Conference on Information-Theoretic Cryptography (ITC 2021)
Issue Date: 2021
Date of publication: 19.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI