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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Brassard, G., Chaum, D., Crépeau, C.: Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences 37(2) (1988)
Blum, M., Santis, A.D., Micali, S., Persiano, G.: Non-interactive zero-knowledge. SIAM Journal of Computing 20(6) (1991)
Bellare, M., Yung, M.: Certifying permutations: non-interactive zero-knowledge based on any trapdoor permutation. J. Cryptology 9(3) (1996)
Fischlin, M.: Trapdoor Commitment Schemes and Their Applications. PhD thesis, University of Frankfurt am Main (December 2001)
Feige, U., Lapidot, D., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Computing 29(1) (1999)
Gennaro, R., Micali, S.: Independent zero-knowledge sets (2005) (Unpublished manuscript)
Goldwasser, S., Micali, S., Rivest, R.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Computing 17(2) (1988)
Goldwasser, S., Ostrovsky, R.: Invariant signatures and non-interactive zero-knowledge proofs are equivalent. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 228–245. Springer, Heidelberg (1992)
Håstad, J., Impagliazzo, R., Levin, L., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Computing 28(4) (1999)
Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 95–107. Springer, Heidelberg (1994)
Lysyanskaya, A.: Unique signatures and verifiable random functions from the DH-DDH separation. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, p. 597. Springer, Heidelberg (2002)
Micali, S., Rabin, M., Kilian, J.: Zero-knowledge sets. In: Proc. 44th IEEE Symposium on Foundations of Computer Science, FOCS (2003)
Micali, S., Rabin, M., Vadhan, S.: Verifiable random functions. In: Proc. 40th IEEE Symposium on Foundations of Computer Science, FOCS (1999)
Naor, M.: Bit commitment using pseudorandomness. Journal of Cryptology 4(2), 51–158 (1991)
Ostrovsky, R., Rackoff, C., Smith, A.: Efficient consistency proof on a committed database. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 1041–1053. Springer, Heidelberg (2004)
Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chase, M., Healy, A., Lysyanskaya, A., Malkin, T., Reyzin, L. (2005). Mercurial Commitments with Applications to Zero-Knowledge Sets. In: Cramer, R. (eds) Advances in Cryptology – EUROCRYPT 2005. EUROCRYPT 2005. Lecture Notes in Computer Science, vol 3494. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11426639_25
Download citation
DOI: https://doi.org/10.1007/11426639_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25910-7
Online ISBN: 978-3-540-32055-5
eBook Packages: Computer ScienceComputer Science (R0)