Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing

Authors: Shai Halevi and Silvio Micali.

Reference: Advances in Cryptology - CRYPTO '96. Lecture Notes in Computer Science, vol. 1109, Pages 201-215, Springer-Verlag, 1996.

Abstract: We present a very practical string-commitment scheme which is provably secure based solely on collision-free hashing. Our scheme enables a computationally bounded party to commit strings to an unbounded one, and is optimal (within a small constant factor) in terms of interaction, communication, and computation.

Our result also proves that constant round statistical zero-knowledge arguments and constant-round computational zero-knowledge proofs for NP exist based on the existence of collision-free hash functions.

Note: A similar construction was described by I. Damgard, T. P. Pedersen and B. Pfitzmann, "On the existance of statistically hiding bit commitment schemes and fail-stop signatures", Advances in Cryptology - CRYPTO '93., Lecture Notes in Computer Science, vol. 773, Pages 250-265, Springer-Verlag, 1993.

Availability: Paper available as Gzipped PostScript (60 Kbyte).


Shai Halevi's home page.