**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.

**Category / Keywords: **foundations / zero-knowledge, non-malleability

**Publication Info: **Extended version of the paper that will appear in the ICALP'06 proceedings

**Date: **received 24 Apr 2006

**Contact author: **rosario at us ibm com

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20060424:204611 (All versions of this report)

**Short URL: **ia.cr/2006/155

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]