Probabilistically Checkable Proofs of Proximity with Zero-Knowledge

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

 ∈ 

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

′ ∈ 

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.

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).

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.