TR07-031 Authors: Yael Tauman Kalai, Ran Raz

Publication: 29th March 2007 11:05

Downloads: 3025

Keywords:

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.