**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$.

**Category / Keywords: **foundations / zero knowledge, pcp, szk

**Date: **received 24 Apr 2012

**Contact author: **david xiao at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20120430:153224 (All versions of this report)

**Short URL: **ia.cr/2012/229

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]