Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-052 | 27th April 2012 21:31

Languages with Efficient Zero-Knowledge PCPs are in SZK



A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in $NEXP$. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, revisited the possibility of efficient ZK-PCPs for all of $NP$ where the PCP is encoded as a polynomial-size circuit that given a query $i$ returns the $i$'th symbol of the PCP. Ishai et al showed that there is no efficient ZK-PCP for $NP$ with non-adaptive verifier, who prepares all of its PCP queries before seeing any answers, unless $NP \subseteq coAM$ and polynomial-time hierarchy collapses. The question of whether adaptive verification can lead to efficient ZK-PCPs for $NP$ remained open.

In this work, we resolve this question and show that any language or promise problem with efficient ZK-PCPs must be in $SZK$ (the class of promise problems with a statistical zero-knowledge single-prover proof system). Therefore, no $NP$-complete problem can have an efficient ZK-PCP unless $NP \subseteq SZK$ (which also implies $NP \subseteq coAM$ and the polynomial-time hierarchy collapses).

We prove our result by reducing any promise problem with an efficient ZK-PCP to two instances of the "Conditional Entropy Approximation" problem defined and studied by Vadhan (FOCS'04) which is known to be complete for the class $SZK$.

ISSN 1433-8092 | Imprint