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 L is an element of NP where the PCP is encoded as a polynomial- size circuit that given a query i returns the ith symbol of the PCP. Ishai et al. showed that there is no efficient ZK-PCP for NP with a non-adaptive verifier, who prepares all of its PCP queries before seeing any answers, unless NP 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 is a subset of SZK (which also implies NP is a subset of 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.