### Composition of Zero-Knowledge Proofs with Efficient Provers

##### Abstract

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)
Category
Foundations
Publication info
Published elsewhere. Extended Abstract to appear in the Theory of Cryptography Conference, 2010.
Keywords
zero knowledge
Contact author(s)
eleanor @ cs cornell edu
History
Short URL
https://ia.cr/2009/604

CC BY

BibTeX

@misc{cryptoeprint:2009/604,
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{https://eprint.iacr.org/2009/604}},
url = {https://eprint.iacr.org/2009/604}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.