Hash Functions: From Merkle-Damgård to Shoup
- 1.7k Downloads
In this paper we study two possible approaches to improving existing schemes for constructing hash functions that hash arbitrary long messages. First, we introduce a continuum of function classes that lie between universal one-way hash functions and collision-resistant functions. For some of these classes efficient (yielding short keys) composite schemes exist. Second, we prove that the schedule of the Shoup construction, which is the most efficient composition scheme for universal one-way hash functions known so far, is optimal.
KeywordsHash Function Success Probability Signature Scheme Compression Function Cryptographic Primitive
- [B82]M. Blum, “Coin flipping by telephone,” CRYPTO 81, pp. 11–15, 1981.Google Scholar
- [BR97]M. Bellare, P. Rogaway, “Collision-resistant hashing: towards making UOWHFs practical,” Proc. of CRYPTO 97, pp. 470–484, Full version of this paper is available from http://www-cse.ucsd.edu/users/mihir/, 1997.
- [D89]I. Damgård, “A design principle for hash functions,” Proc. of CRYPTO 89, pp. 416–427, 1989.Google Scholar
- [GT00]R. Gennaro, L. Trevisan, “Lower bounds on the efficiency of generic cryptographic constructions,” Proc. of FOCS'00, pp. 305–313, 2000.Google Scholar
- [KST99]J.H. Kim, D. Simon, P. Tetali, “Limits on the efficiency of one-way permutation-based hash functions,” Proc. of FOCS'99, pp. 535–542, 1999.Google Scholar
- [LM92]X. Lai, J. Massey, “Hash function based on block ciphers,” Proc. of EUROCRYPT 92, pp. 55–70, 1992.Google Scholar
- [M89]R. Merkle, “One way hash functions and DES,” Proc. of CRYPTO 89, pp. 428–446, 1989.Google Scholar
- [NY89]M. Naor, M. Yung, “Universalone-w ay hash functions and their cryptographic applications,” Proc. of STOC'89, pp. 33–43, 1989.Google Scholar
- [Ro90]J. Rompel, “One-way functions are necessary and sufficient for secure signatures,” Proc. of STOC'90, pp. 387–394, 1990.Google Scholar
- [SS00]T. Schweinberger, V. Shoup, “ACE: The Advanced Cryptographic Engine,” Manuscript. Available from http://www.shoup.net, 2000.
- [Sh00]V. Shoup, “A composite theorem for universalone-w ay hash functions,” Proc. of EUROCRYPT 2000, pp. 445–452, 2000.Google Scholar
- [Si98]D. Simon, “Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?” Proc. of EUROCRYPT 98, pp. 334–345, 1998.Google Scholar
- [ZMI90]Y. Zheng, T. Matsumoto, H. Imai, “Structuralprop erties of one-way hash functions,” Proc. of Crypto 90, pp. 285–302, 1990.Google Scholar