###
Mercurial Commitments with Applications to Zero-Knowledge Sets

by Melissa Chase,
Alexander Healy,
Anna Lysyanskaya,
Tal Malkin,
and Leonid Reyzin

**Abstract**
We introduce a new flavor of commitment schemes, which we call
*mercurial commitments*. Informally, mercurial commitments are
standard commitments that have been extended to allow for *soft*
decommitment. Soft decommitments, on the one hand, are not binding
but, on the other hand, cannot be in conflict with true decommitments.

We then demonstrate that a
particular instantiation of mercurial commitments has been implicitly
used by Micali, Rabin and Kilian to construct *zero-knowledge
sets*. (A *zero-knowledge set* scheme allows a Prover to (1)
commit to a set *S* in a way that reveals nothing about *S* and (2)
prove to a Verifier, in zero-knowledge, statements of the form "*x* is in
*S*" and "*x* is not in *S*.") The rather complicated construction of Micali et
al. becomes easy to understand when viewed as a more general
construction with mercurial commitments as an underlying building
block.

By providing mercurial
commitments based on various assumptions, we obtain several different
new zero-knowledge set constructions.

A preliminary version of this work appears in Advances in Cryptology -- EUROCRYPT 2005, Ronald Cramer
editor, Lecture Notes in Computer Science 3494, Springer-Verlag, 2005, pp. 422-439.
© IACR. This is the full version, Journal of Cryptology 2013, © by the authors.