Hash Functions: From Merkle-Damgård to Shoup

  • Ilya Mironov
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


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.


Hash Function Success Probability Signature Scheme Compression Function Cryptographic Primitive 
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.


  1. [B82]
    M. Blum, “Coin flipping by telephone,” CRYPTO 81, pp. 11–15, 1981.Google Scholar
  2. [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, 1997.
  3. [D89]
    I. Damgård, “A design principle for hash functions,” Proc. of CRYPTO 89, pp. 416–427, 1989.Google Scholar
  4. [GT00]
    R. Gennaro, L. Trevisan, “Lower bounds on the efficiency of generic cryptographic constructions,” Proc. of FOCS'00, pp. 305–313, 2000.Google Scholar
  5. [HILL99]
    J. Hastad, R. Impagliazzo, L. Levin, M. Luby, ”A pseudo-random generator from any one-way function,” SIAM J. Computing, 28(4):1364–1396, 1999.zbMATHCrossRefMathSciNetGoogle Scholar
  6. [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
  7. [LM92]
    X. Lai, J. Massey, “Hash function based on block ciphers,” Proc. of EUROCRYPT 92, pp. 55–70, 1992.Google Scholar
  8. [M89]
    R. Merkle, “One way hash functions and DES,” Proc. of CRYPTO 89, pp. 428–446, 1989.Google Scholar
  9. [N91]
    M. Naor, “Bit commitment using pseudorandomness,” J. Cryptology, 4(2): 151–158, 1991.zbMATHCrossRefGoogle Scholar
  10. [NY89]
    M. Naor, M. Yung, “Universalone-w ay hash functions and their cryptographic applications,” Proc. of STOC'89, pp. 33–43, 1989.Google Scholar
  11. [Ro90]
    J. Rompel, “One-way functions are necessary and sufficient for secure signatures,” Proc. of STOC'90, pp. 387–394, 1990.Google Scholar
  12. [Ru95]
    A. Russell, “Necessary and sufficient condtions for collision-free hashing,” J. of Cryptology 8(2), pp. 87–100, 1995.zbMATHGoogle Scholar
  13. [SS00]
    T. Schweinberger, V. Shoup, “ACE: The Advanced Cryptographic Engine,” Manuscript. Available from, 2000.
  14. [Sh00]
    V. Shoup, “A composite theorem for universalone-w ay hash functions,” Proc. of EUROCRYPT 2000, pp. 445–452, 2000.Google Scholar
  15. [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
  16. [ZMI90]
    Y. Zheng, T. Matsumoto, H. Imai, “Structuralprop erties of one-way hash functions,” Proc. of Crypto 90, pp. 285–302, 1990.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Ilya Mironov
    • 1
  1. 1.Computer Science DepartmentStanford UniversityStanford

Personalised recommendations