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.