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).
Category / Keywords: Date: received 6 May 2013, last revised 20 Jan 2015 Contact author: luied at cs cornell edu Available format(s): PDF | BibTeX Citation Version: 20150120:222925 (All versions of this report) Discussion forum: Show discussion | Start new discussion