[GK96] On the Composition of Zero-Knowledge Proof Systems

Authors: Oded Goldreich, Hugo Krawczyk | Venue: SIAM Journal on Computing 1996 | Source

Abstract

We investigate the behavior of zero-knowledge proofs under composition. Our main negative result is that three-round black-box zero-knowledge proof systems for NP exist only if NP ⊆ BPP: no language outside BPP has a constant-round (in particular, three-round) black-box simulation zero-knowledge proof system unless the polynomial hierarchy collapses. This shows a fundamental limitation: the round complexity of zero-knowledge proofs cannot be made constant in general. We also study the composition of zero-knowledge protocols in sequential and parallel settings, showing that sequential composition preserves zero-knowledge but parallel composition may not.

BibTeX

Copy

@article{GK96,
  author  = {Oded Goldreich and Hugo Krawczyk},
  title   = {On the Composition of Zero-Knowledge Proof Systems},
  journal = {SIAM Journal on Computing},
  volume  = {25},
  number  = {1},
  pages   = {169--192},
  year    = {1996}
}