Languages with Efficient Zero-Knowledge PCPs are in SZK
Purchase on  $29.95 / €24.95 / £19.95*  * Final gross prices may
vary according to local VAT.  Get Access   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