Paper 2013/260

From Weak to Strong Zero-Knowledge and Applications

Kai-Min Chung, Edward Lui, and Rafael Pass


The notion of \emph{zero-knowledge} \cite{GMR85} is formalized by requiring that for every malicious efficient verifier $V^*$, there exists an efficient simulator $S$ that can reconstruct the view of $V^*$ in a true interaction with the prover, in a way that is indistinguishable to \emph{every} polynomial-time distinguisher. \emph{Weak zero-knowledge} weakens this notions by switching the order of the quantifiers and only requires that for every distinguisher $D$, there exists a (potentially different) simulator $S_D$. In this paper we consider various notions of zero-knowledge, and investigate whether their weak variants are equivalent to their strong variants. Although we show (under complexity assumption) that for the standard notion of zero-knowledge, its weak and strong counterparts are not equivalent, for meaningful variants of the standard notion, the weak and strong counterparts are indeed equivalent. Towards showing these equivalences, we introduce new non-black-box simulation techniques permitting us, for instance, to demonstrate that the classical 2-round graph non-isomorphism protocol of Goldreich-Micali-Wigderson \cite{GMW91} satisfies a ``distributional'' variant of zero-knowledge. Our equivalence theorem has other applications beyond the notion of zero-knowledge. For instance, it directly implies the \emph{dense model theorem} of Reingold et al (STOC '08), and the leakage lemma of Gentry-Wichs (STOC '11), and provides a modular and arguably simpler proof of these results (while at the same time recasting these result in the language of zero-knowledge).

Available format(s)
Publication info
Published elsewhere. Unknown status
Contact author(s)
luied @ cs cornell edu
2015-01-20: last of 2 revisions
2013-05-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kai-Min Chung and Edward Lui and Rafael Pass},
      title = {From Weak to Strong Zero-Knowledge and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2013/260},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.