Probabilistically Checkable Proofs With Zero Knowledge
Mor Weiss


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 \emph{PCP of proximity} (PCPP) has the additional feature of allowing the verifier to query only few bits of the {\em input} $x$, where if the input is accepted then the verifier is guaranteed that (with high probability) the input is \emph{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 \emph{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.

Based on a joint work with Yuval Ishai.