Technical Report CS0570

Title: On the Composition of Zero-Knowledge Proof Systems
Authors: O. Goldreich and H. Krawczyk
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 conjuctered by many researchers (leading to the introduction of more robust fonnulations of zero-knowledge (e.g. black-box simulation), but no full proof has been given yet.

We prove that the general statement that the parallel composition of any two zeroknowledge protocols constitutes a zero-knowledge protocol, is wrong. Namely, we present two protocols, both being zero-Knowledge in a strong sense (e.g. black-box simulation) yet their parallel composition is not zero-knowledge (not even in a weak sense). We resolve an open problem concerning the "parallel versions" of the interactive proofs systems known for quadratic residuosity, graph isomorphism and any language in NP. We show that these proof systems (which are constant-round Arthur-Merlin games) cannot be proven zero-knowledge using black-box simulation, unless the corresponding languages are in BPP. This is a corollary of our result that a constant-round Arthur Merlin interactive. proof for a language L, cannot be proven zero-knowledge using black-box simulation, unless L is in BPP. It should be noted that all known zeroknowledge interactive proofs are proven zero-knowledge using black-box simulation and that it is hard to conceive an alternative way for demonstrating the zero-knowledgeness of an interactive proof. The result concerning Arthur-Merlin zero-knowledge proofs can be viewed as a support to the conjecture that "secret coins" help in the zero-knowledge setting.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion