Paper 2005/438

Minimal Assumptions for Efficient Mercurial Commitments

Yevgeniy Dodis

Abstract

Mercurial commitments were introduced by Chase et al. (Eurocrypt 2005) and form a key building block for constructing zero-knowledge sets (introduced by Micali, Rabin and Kilian (FOCS'03)}). Unlike regular commitments, which are strictly binding, mercurial commitments allow for certain amount of (limited) freedom. The notion of Chase et al. also required that mercurial commitments should be equivocable given a certain trapdoor, although the notion is interesting even without this condition. While trivially implying regular (trapdoor) commitments, it was not clear from the prior work if the converse was true: Chase et al. gave several constructions of mercurial commitments from various incompatible assumptions, leaving open if they can be built from any (trapdoor) commitment scheme, and, in particular, from any one-way function. We give an affirmative answer to this question, by giving two simple constructions of mercurial commitments from any trapdoor bit commitment scheme. By plugging in various (trapdoor) bit commitment schemes, we get *all* the efficient constructions from Chase et al. and Micali et al., as well as several immediate new constructions. Our results imply that (a) ** mercurial commitments can be viewed as surprisingly simple variations of regular (trapdoor) commitments ** (and, thus, can be built from one-way functions and, more efficiently, from a variety of other assumptions); and (b) ** the existence of zero-knowledge sets is equivalent to the existence of collision-resistant hash functions ** (moreover, the former can be efficiently built from the latter and trapdoor commitments). Of independent interest, we also give a stronger and yet much simpler definition of mercurial commitments than that of Chase et al. (which is also met by our constructions). Overall, we believe that our results eludicate the notion of mercurial commitments, and better explain the rational following the previous constructions of mercurial commitments.

Note: This is an independent part of the merged TCC 2006 paper by Dario Catalano, Yevgeniy Dodis and Ivan Visconti, "Mercurial Commitments: Minimal Assumptions and Efficient Constructions", Theory of Cryptography Conference (TCC), March 2006. The included part is by Yevgeniy Dodis, and the missing part is from Dario Catalano, Ivan Visconti "Non-Interactive Mercurial Commitments from One-Way Functions" ECRYPT Technical Report, 2005.