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 $\text{NEXP}$. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, revisited the possibility of \emph{efficient} ZK-PCPs for all $$ where the PCP is encoded as a polynomial-size circuit that given a query $$ returns the $$ symbol of the PCP. Ishai \etal showed that there is no efficient ZK-PCP for $$ with a \emph{non-adaptive} verifier, who prepares all of its PCP queries before seeing any answers, unless $$ and polynomial-time hierarchy collapses. The question of whether \emph{adaptive} verification can lead to efficient ZK-PCPs for $$ remained open. In this work, we resolve this question and show that any language or promise problem with efficient ZK-PCPs must be in $$ (the class of promise problems with a statistical zero-knowledge \emph{single prover} proof system). Therefore, no $$-complete problem can have an efficient ZK-PCP unless $$ (which also implies $$ 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 $$ problem defined and studied by Vadhan (FOCS'04) which is known to be complete for the class $$.