Paper 2012/229

Languages with Efficient Zero-Knowledge PCP's are in SZK

Mohammad Mahmoody and David Xiao

Abstract

A \emph{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 \emph{efficient} ZK-PCPs for all $L \in \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 \etal showed that there is no efficient ZK-PCP for $\NP$ with a \emph{non-adaptive} verifier, who prepares all of its PCP queries before seeing any answers, unless $\NP \se \coAM$ and polynomial-time hierarchy collapses. The question of whether \emph{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 \emph{single prover} proof system). Therefore, no $\NP$-complete problem can have an efficient ZK-PCP unless $\NP \se \SZK$ (which also implies $\NP \se \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 $\CEA$ problem defined and studied by Vadhan (FOCS'04) which is known to be complete for the class $\SZK$.