On the 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.