Paper 2001/020

Some observations on the theory of cryptographic hash functions

D. R. Stinson

Abstract

In this paper, we study several issues related to the notion of ``secure'' hash functions. Several necessary conditions are considered, as well as a popular sufficient condition (the so-called random oracle model). We study the security of various problems that are motivated by the notion of a secure hash function. These problems are analyzed in the random oracle model, and we prove that the obvious trivial algorithms are optimal. As well, we look closely at reductions between various problems. In particular, we consider the important question ``does preimage resistance imply collision resistance?''. Finally, we study the relationship of the security of hash functions built using the Merkle-Damgard construction to the security of the underlying compression function.

Metadata
Available format(s)
PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
hash functions
Contact author(s)
dstinson @ uwaterloo ca
History
2001-03-02: received
Short URL
https://ia.cr/2001/020
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/020,
      author = {D. R.  Stinson},
      title = {Some observations on the theory of cryptographic hash functions},
      howpublished = {Cryptology ePrint Archive, Paper 2001/020},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/020}},
      url = {https://eprint.iacr.org/2001/020}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.