TR12-052 Authors: Mohammad Mahmoody, David Xiao

Publication: 27th April 2012 23:00

Downloads: 1521

Keywords:

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