Accession Number:

ADA582593

Title:

On the Composition of Public-Coin Zero-Knowledge Protocols

Descriptive Note:

Technical paper

Corporate Author:

CORNELL UNIV ITHACA NY DEPT OF COMPUTER SCIENCE

Report Date:

2011-05-31

Pagination or Media Count:

27.0

Abstract:

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.

Descriptors:

Subject Categories:

  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE