Non-interactive mercurial commitments from one-way functions - E-CRYPT (PROVILAB

At Eurocrypt 2005 Chase et al. introduced the notion of mercurial commitment schemes. The main application of mercurial commitments is that, used together with collision resistant hash functions, they suffice to construct zero-knowledge sets (ZKS), introduced by Micali et al. at FOCS 2003. In particular, Chase et al. show how to construct non-interactive mercurial commitments in the so called shared random string model under the assumption that non-interactive zero-knowledge proofs exist. Their result implies that one can construct non-interactive zero-knowledge sets, in the shared random string model, from the assumptions that collision resistant hash functions and non-interactive zero-knowledge proofs exist. The same result was independently achieved by Ostrovsky et al. at ICALP 2004. These two results can be seen as initial solutions to the problem, left open by Micali et al., of reducing the computational assumptions required to construct non-interactive zero-knowledge sets in the shared random string model. However, the problem of determining the exact complexity of non-interactive mercurial commitments and zero-knowledge sets in the shared random string model, is still open. In this paper we solve this problem by showing how to construct non-interactive mercurial commitments in the shared random string model, under the sole assumption that one-way functions exist. This, combined with the results of Chase et al., allows us to prove that (in the shared random string model) non-interactive zero-knowledge sets are actually equivalent to collision-resistant hash functions