Independent Zero-Knowledge Sets

Rosario Gennaro; Silvio Micali

Paper 2006/155

Independent Zero-Knowledge Sets

Rosario Gennaro and Silvio Micali

Abstract

We define and construct Independent Zero-Knowledge Sets (ZKS) protocols. In a ZKS protocols, a Prover commits to a set $S$, and for any $x$, proves non-interactively to a Verifier if $x \in S$ or $x \notin S$ without revealing any other information about $S$. In the {\em independent} ZKS protocols we introduce, the adversary is prevented from successfully correlate her set to the one of a honest prover. Our notion of independence in particular implies that the resulting ZKS protocol is non-malleable. On the way to this result we define the notion of {\em independence} for commitment schemes. It is shown that this notion implies non-malleability, and we argue that this new notion has the potential to simplify the design and security proof of non-malleable commitment schemes. Efficient implementations of ZKS protocols are based on the notion of mercurial commitments. Our efficient constructions of independent ZKS protocols requires the design of {\em new} commitment schemes that are simultaneously independent (and thus non-malleable) and mercurial.

Metadata

Available format(s): PS
Category: Foundations
Publication info: Published elsewhere. Extended version of the paper that will appear in the ICALP'06 proceedings
Keywords: zero-knowledge non-malleability
Contact author(s): rosario @ us ibm com
History: 2006-04-24: received
Short URL: https://ia.cr/2006/155
License: CC BY

BibTeX

@misc{cryptoeprint:2006/155,
      author = {Rosario Gennaro and Silvio Micali},
      title = {Independent Zero-Knowledge Sets},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/155},
      year = {2006},
      url = {https://eprint.iacr.org/2006/155}
}