*18:17*[Pub][ePrint] Languages with Efficient Zero-Knowledge PCP\'s are in SZK, by Mohammad Mahmoody and David Xiao

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