[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.