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.
Category / Keywords: Probabilistically Checkable Proofs, Zero-Knowledge, Verifiable Secret Sharing Original Publication (in the same form): IACR-TCC-2014 Date: received 21 Feb 2017, last revised 21 Feb 2017 Contact author: mormorweiss at gmail com Available format(s): PDF | BibTeX Citation Version: 20170227:145135 (All versions of this report) Short URL: ia.cr/2017/176 Discussion forum: Show discussion | Start new discussion