Paper 2017/176

Probabilistically Checkable Proofs of Proximity with Zero-Knowledge

Yuval Ishai and Mor Weiss

Abstract

A probabilistically Checkable Proof (PCP) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form "$x\in L$" by querying only few bits of the proof. A PCP of proximity (PCPP) has the additional feature of allowing the verifier to query only few bits of the input $x$, where if the input is accepted then the verifier is guaranteed that (with high probability) the input is close to some $x'\in L$. Motivated by their usefulness for sublinear-communication cryptography, we initiate the study of a natural zero-knowledge variant of PCPP (ZKPCPP), where the view of any verifier making a bounded number of queries can be efficiently simulated by making the same number of queries to the input oracle alone. This new notion provides a useful extension of the standard notion of zero-knowledge PCPs. We obtain two types of results. 1. Constructions. We obtain the first constructions of query-efficient ZKPCPPs via a general transformation which combines standard query-efficient PCPPs with protocols for secure multiparty computation. As a byproduct, our construction provides a conceptually simpler alternative to a previous construction of honest-verifier zero-knowledge PCPs due to Dwork et al. (Crypto '92). 2. Applications. We motivate the notion of ZKPCPPs by applying it towards sublinear-communication implementations of commit-and-prove functionalities. Concretely, we present the first sublinear-communication commit-and-prove protocols which make a black-box use of a collision-resistant hash function, and the first such multiparty protocols which offer information-theoretic security in the presence of an honest majority.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCC 2014
Keywords
Probabilistically Checkable ProofsZero-KnowledgeVerifiable Secret Sharing
Contact author(s)
mormorweiss @ gmail com
History
2017-02-27: received
Short URL
https://ia.cr/2017/176
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/176,
      author = {Yuval Ishai and Mor Weiss},
      title = {Probabilistically Checkable Proofs of Proximity with Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2017/176},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/176}},
      url = {https://eprint.iacr.org/2017/176}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.