On Efficient Zero-Knowledge PCPs

We revisit the question of

Zero-Knowledge PCPs

, studied by Kilian, Petrank, and Tardos (STOC ’97). A ZK-PCP is defined similarly to a standard PCP, except that the view of any (possibly malicious) verifier can be efficiently simulated up to a small statistical distance. Kilian et al.obtained a ZK-PCP for

NEXP

in which the proof oracle is in

EXP

NP

. They also obtained a ZK-PCP for

NP

in which the proof oracle is computable in polynomial-time, but this ZK-PCP is only zero-knowledge against

bounded-query

verifiers who make at most an

a priori fixed

polynomial number of queries. The existence of ZK-PCPs for

NP

with efficient oracles and arbitrary polynomial-time malicious verifiers was left open. This question is motivated by the recent line of work on cryptography using tamper-proof hardware tokens: an efficient ZK-PCP (for any language) is

equivalent

to a statistical zero-knowledge proof using only a single stateless token sent to the verifier.

We obtain the following results regarding efficient ZK-PCPs:

Negative Result on Efficient ZK-PCPs.

Assuming that the polynomial time hierarchy does not collapse, we settle the above question in the negative for ZK-PCPs in which the verifier is

nonadaptive

(i.e. the queries only depend on the input and secret randomness but not on the PCP answers).

Simplifying Bounded-Query ZK-PCPs.

The bounded-query zero-knowledge PCP of Kilian et al. starts from a

weakly-sound

bounded-query ZK-PCP of Dwork et al. (CRYPTO ’92) and amplifies its soundness by introducing and constructing a new primitive called

locking scheme

— an unconditional oracle-based analogue of a commitment scheme. We simplify the ZK-PCP of Kilian et al. by presenting an elementary new construction of locking schemes. Our locking scheme is purely combinatorial.

Black-Box Sublinear ZK Arguments via ZK-PCPs.

Kilian used PCPs to construct sublinear-communication zero-knowledge arguments for

NP

which make a

non-black-box

use of collision-resistant hash functions (STOC ’92). We show that ZK-PCPs can be used to get black-box variants of this result with improved round complexity, as well as an

unconditional

zero-knowledge variant of Micali’s non-interactive CS Proofs (FOCS ’94) in the Random Oracle Model.