On the composition of zero-knowledge proof systems

Abstract

A basic question concerning zero-knowledge proof systems is whether their (sequential and/or parallel) composition is zero-knowledge too. This question is not only of natural theoretical interest, but is also of great practical importance as it concerns the use of zero-knowledge proofs as subroutines in cryptographic protocols.

We prove that the original formulation of zero-knowledge as appearing in the pioneering work of Goldwasser, Micali and Rackoff is not closed under sequential composition. This fact was conjectured by many researchers leading to the introduction of stronger formulations of zero-knowledge (e.g. black-box simulation). We also prove that the parallel composition of zero-knowledge protocols does not necessarily result in a new zero-knowledge protocol: we present two protocols, both being zero-knowledge in a strong sense yet their parallel composition is not zero-knowledge (not even in a weak sense).

We present a lower bound on the round complexity of zero-knowledge proofs. We prove that only BPP languages have 3-round interactive proofs which are black-box simulation zero-knowledge. Moreover, we show that languages having constant-round Arthur-Merlin proofs that are black-box simulation zero-knowledge are in BPP. These results have significant implications to the parallelization of zero-knowledge proofs. In particular it follows that the "parallel versions" of the original interactive proofs systems for quadratic residuosity, graph isomorphism and any language in NP, are not black-box simulation zero-knowledge, unless the corresponding languages are in BPP. This resolves an open problem arising from the early works on zero-knowledge. Other consequences are a proof of optimality for the round complexity of various known zero-knowledge protocols, and a structure theorem for the hierarchy of Arthur-Merlin zero-knowledge languages.

Extended Abstract

Research was partially supported by the Fund for Basic Research Administered by the Israeli Academy of Sciences and Humanities.