Abstract:
An interactive-PCP (say, for the membership $x \in L$) is a proof that can be verified by reading only one of its bits, with the help of a very short interactive-proof. We show that for membership in some languages $L$, there are interactive-PCPs that are significantly shorter than the known (non-interactive) PCPs for these languages. Our main result is that the satisfiability of a constant depth Boolean formula $\Phi(z_1,\ldots,z_k)$ of size $n$ (over the gates $\wedge, \vee, \oplus, \neg $) can be proved by an interactive-PCP of size $\poly(k)$, followed by a short interactive proof of communication complexity $\polylog(n)$. That is, we obtain interactive-PCPs of size polynomial in the size of the witness. This compares to the known (non-interactive) PCPs that are of size polynomial in the size of the instance. By reductions, this result extends to many other central NP languages (e.g., SAT, $k$-clique, Vertex-Cover, etc.). More generally, we show that the satisfiability of $\bigwedge_{i=1}^n[\Phi_i(z_1,\ldots,z_k) =0]$, where each $\Phi_i(z_1,\ldots,z_k)$ is an arithmetic formula of size $n$ (say, over $\mathbb{GF}[2]$) that computes a polynomial of degree $d$, can be proved by an interactive-PCP of size $\poly(k,d)$, followed by a short interactive proof of communication complexity $\poly(d,\log n)$. We give many cryptographic applications and motivations for our results. In particular, we show the following: The satisfiability of a constant depth formula $\Phi(z_1,\ldots,z_k)$ of size $n$ (as above) has an interactive zero-knowledge {\em proof} of communication complexity $\poly(k)$ (rather than $\poly(n)$)\footnote{We have learnt that a similar result was proved independently (and more or less at the same time) by Ishai, Kushilevitz, Ostrovsky and Sahai~\cite{IKOS}.}. As before, this result extends to many other central NP languages. This zero-knowledge proof has some additional desired properties that will be elaborated on in the body of the paper. Alice can commit to a Boolean formula $\Lambda$ of size $m$, by a message of size $\poly(m)$, and later on prove to Bob any $N$ statements of the form $\Lambda(x_1)=z_1,\ldots,\Lambda(x_N)=z_N$ by a zero-knowledge {\em proof} of communication complexity $\poly(m, \log N)$. Moreover, if $\Lambda$ is a constant depth Boolean formula then the zero-knowledge proof has communication complexity $\poly(\log m, \log N)$. We further motivate this application in the body of the paper.