On the Composition of Public-Coin Zero-Knowledge Protocols

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 31, 2011
Accession Number
ADA582593

Entities

People

  • Douglas Wikstroem
  • Rafael Pass
  • Wei-lung D. Tseng

Organizations

  • Cornell University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Amplification
  • Automata
  • Computer Science
  • Cryptography
  • Inequalities
  • Iterations
  • Language
  • Machines
  • Notation
  • Polynomials
  • Probability
  • Probability Distributions
  • Random Variables
  • Simulations
  • Simulators
  • Standards

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Computer Engineering
  • Cybersecurity.
  • Mathematical Modeling and Probability Theory.