Probabilistically Checkable Proofs (PCPs) allow a verifier

to check the validity of a proof by querying very few random

positions in the proof string. Zero Knowledge (ZK) Proofs allow a

prover to convince a verifier of a statement without revealing any

information beyond the validity of the statement. We study for what

class of languages it is possible to achieve both, namely to build

ZK-PCPs, where additionally we require that the proof be generated

efficiently. Such ZK-PCPs could potentially be useful for building UC-secure

protocols in the tamper-proof token model.

We show that all languages with efficient statistical ZK-PCPs

(i.e. where the ZK property holds against unbounded verifiers) must

be in SZK (the class of languages with interactive statistical ZK

proofs). We do this by reducing any ZK-PCP to an instance of the

Conditional Entropy Approximation problem, which is known to be

in SZK. This implies in particular that such ZK-PCPs are unlikely to exist

for NP-complete problems such as SAT.

This is joint work with Mohammad Mahmoody.