Paper 2009/604

Composition of Zero-Knowledge Proofs with Efficient Provers

Eleanor Birrell and Salil Vadhan


We revisit the composability of different forms of zero-knowledge proofs when the honest prover strategy is restricted to be polynomial time (given an appropriate auxiliary input). Our results are: \begin{enumerate} \item When restricted to efficient provers, the original Goldwasser--Micali--Rackoff (GMR) definition of zero knowledge (STOC `85), here called \emph{plain zero knowledge}, is closed under a constant number of sequential compositions (on the same input). This contrasts with the case of unbounded provers, where Goldreich and Krawczyk (ICALP `90, SICOMP `96) exhibited a protocol that is zero knowledge under the GMR definition, but for which the sequential composition of 2 copies is not zero knowledge. \item If we relax the GMR definition to only require that the simulation is indistinguishable from the verifier's view by uniform polynomial-time distinguishers, with no auxiliary input beyond the statement being proven, then again zero knowledge is not closed under sequential composition of 2 copies. \item We show that auxiliary-input zero knowledge with efficient provers is not closed under {\em parallel} composition of 2 copies under the assumption that there is a secure key agreement protocol (in which it is easy to recognize valid transcripts). Feige and Shamir (STOC `90) gave similar results under the seemingly incomparable assumptions that (a) the discrete logarithm problem is hard, or (b) $\UP\not\subseteq \BPP$ and one-way functions exist. \end{enumerate}

Available format(s)
Publication info
Published elsewhere. Extended Abstract to appear in the Theory of Cryptography Conference, 2010.
zero knowledge
Contact author(s)
eleanor @ cs cornell edu
2009-12-09: received
Short URL
Creative Commons Attribution


      author = {Eleanor Birrell and Salil Vadhan},
      title = {Composition of Zero-Knowledge Proofs with Efficient Provers},
      howpublished = {Cryptology ePrint Archive, Paper 2009/604},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.