International Association
for Cryptologic Research

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∈S and x∉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.

• Content Type Journal Article
• Pages 1-29
• DOI 10.1007/s00145-012-9122-9
• Authors

  • Melissa Chase, Microsoft Research, Redmond, WA 98052, USA
  • Alexander Healy, Division of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA
  • Anna Lysyanskaya, Department of Computer Science, Brown University, Providence, RI 02912, USA
  • Tal Malkin, Department of Computer Science, Columbia University, New York, NY 10027, USA
  • Leonid Reyzin, Department of Computer Science, Boston University, Boston, MA 02215, USA

• Journal Journal of Cryptology
• Online ISSN 1432-1378
• Print ISSN 0933-2790

From: Wed, 28 Mar 2012 05:59:34 GMT