Composition of Public-Coin Zero-Knowledge Protocols.

摘要

We show that only languages in BPP have public-coin black-box zero- knowledge protocols that are secure under an unbounded (polynomial) number of parallel repetitions. This result holds both in the plain model (without any set-up) and in the Bare Public-Key Model (where the prover and the verifier have registered public keys). We complement this result by constructing a public-coin black-box zero-knowledge proof based on one-way functions that remains secure under any a-priori bounded number of concurrent executions. A key step (of independent interest) in the analysis of our lower bound shows that any public coin protocol, when repeated sufficiently in parallel, satisfies a notion of 'resettable soundness' if the verifier picks its random coins using a pseudorandom function.