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.
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
C.H. Bennett and G. Brassard Quantum Cryptography: Public Key Distribution and Coin Tossing. In Proc. of IEEE International Conf. on Computers, Systems, and Signal Processing, IEEE, 1984, pages 175–179.
G. Bleumer, B. Pfitzmann and M. Waidner. A Remark on a Signature Scheme where Forgery can be Proved. In I.B. Damgård, editor, Proc. of Eurocrypt’90, Lecture Notes in Computer Science, volume 473, Springer-Verlag, 1990. pages 441–445.
M. Blum. Coin flipping by telephone. In Proc. IEEE Spring COMPCOM, pages 133–137. IEEE, 1982.
G. Brassard and C. Crèpeau. Nontransitive Transfer of Confidence: A Perfect Zero-Knowledge Interactive Protocol for SAT and Beyond. In Proc. 27th IEEE Symp. on Foundations of Comp. Science, IEEE, 1986, pages 188–195.
G. Brassard and C. Crèpeau. Quantum bit commitment and coin tossing protocols. In A.J. Menezes and S.A. Vanstone, editors, Proc. Crypto’ 90, Lecture Notes in Computer Science, volume 537. Springer-Verlag, 1991, pages 49–61.
G. Brassard, C. Crèpeau, R. Jozsa and D. Langlois. A Quantum Bit Commitment Scheme Provably Unbreakable by Both Parties. In Proc. 34th IEEE Symp. on Foundations of Comp. Science, IEEE, 1993.
L. Carter and M. Wegman. Universal Hash Functions. J. of Computer and System Science 18, 143–154 (1979).
D. Chaum, E. van Heijst and B. Pfitzmann. Cryptographically Strong Undeniable Signatures, Unconditionally Secure for the Signer. In J. Feigenbaum, editor, Proc. Crypto’ 91, Lecture Notes in Computer Science, volume 576, Springer-Verlag, 1992. pages 470–484.
I.B. Damgård, Practical and Provably Secure Release of a Secret and Exchange of Signatures. T. Helleseth, editor, Proc. EuroCrypt’ 93, Lecture Notes in Computer Science, volume 765, Springer-Verlag, 1994, pages 200–217.
I.B. Damgård, T.P. Pedersen, and B. Pfitzmann. On the existence of statistically hiding bit commitment schemes and fail-stop signatures. In D.R. Stinson, editor, Proc. Crypto’ 93, Lecture Notes in Computer Science, volume 773. Springer, 1994. pages 250–265.
O. Goldreich and A. Kahan. How to Construct Constant-Round Zero-Knowledge Proofs Systems for NP. Journal of Cryptology, Vol. 9, No. 2, 1996.
S. Goldwasser, S. Micali, and R. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Computing, 17(2):281–308, April 1988.
Moti Yung and Russell Impagliazzo. Direct minimum-knowledge computations. In C. Pomerance, editor, Proc. Crypto’ 87, Lecture Notes in Computer Science, volume 293, Springer-Verlag, 1988. Pages 40–51.
S. Halevi, Efficient commitment with bounded sender and unbounded receiver. In D. Coppersmith, editor, Proc. Crypto’ 95. Lecture Notes in Computer Science, volume 963, Springer-Verlag, 1995. pages 84–96.
M. Naor. Bit commitment using pseudo-randomness. In G. Brassard, editor, Proc. Crypto’ 89, Lecture Notes in Computer Science, volume 435. Springer-Verlag, 1990. pages 128–137.
M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung. Perfect zero-knowledge arguments for NP can be based on general complexity assumptions. In Ernest F. Brickell, editor, Proc. Crypto’ 92, Lecture Notes in Computer Science, volume 740, Springer-Verlag, 1993. pages 196–214.
M. Naor and M. Yung. Universal One-Way Hash Functions and their Cryptographic Applications. In Proc. 21st ACM Symp. on Theory of Computing, ACM, 1989. pages 33–43.
T.P. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In J. Feigenbaum, editor, Proc. Crypto’ 91, Lecture Notes in Computer Science, volume 576, Springer-Verlag, 1992. pages 129–140.
Federal Information Processing Standards, Publication 180. Specifications for a Secure Hash Standard (SHS).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Halevi, S., Micali, S. (1996). Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing. In: Koblitz, N. (eds) Advances in Cryptology — CRYPTO ’96. CRYPTO 1996. Lecture Notes in Computer Science, vol 1109. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68697-5_16
Download citation
DOI: https://doi.org/10.1007/3-540-68697-5_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61512-5
Online ISBN: 978-3-540-68697-2
eBook Packages: Springer Book Archive