Languages with Efficient Zero-Knowledge PCPs are in SZK

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

t

h

symbol of the PCP. Ishai

et al

showed that there is no efficient ZK-PCP for

NP

with a

non-adaptive

verifier, that prepares all of its PCP queries before seeing any answers, unless

NP

 ⊆ 

coAM

and the 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

 ⊆ 

SZK

(which also implies

NP

 ⊆ 

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

.