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
Personal Author(s):
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