Difference between "one-way function" and "cryptographic hash function"

Question

What's the difference between a one-way function and a cryptographic hash function?

Answer 1

It's all a matter of definitions.

Typically, a "cryptographic hash function" $H$ has three properties:

1. Preimage resistance: Given $H(x)$, it's hard to find $x$
2. Second preimage resistance: Given $m_1$, it's hard to find another $m_2$ such that $H(m_1) = H(m_2)$
3. Collision resistance: It's hard to find any two distinct messages $m_1$, $m_2$ such that $H(m_1) = H(m_2)$.

These aren't definitions that are set in stone. This sort of broad definition is not really very nuanced, but it is indeed a common one. Usually, it's not necessary to be any more specific than this.

For a less restricted definition, you might say a hash function $H$ only has two properties:

  a.  Easy to compute: Given $x$, it is easy to compute $H(x)$
  b.  Compresses: $H : \{0,1\}^{*} \to \{0,1\}^n$ (i.e., it maps any bit-length string to a fixed bit-length)

And then from there you can become more nuanced. Now you can say a "one-way" hash function is a hash function (using the less restricted definition) that possesses properties 1 and 2; that is, it is an easy-to-compute compression function that possesses preimage resistance and second-preimage resistance. In other words, the function can only be computed "one way".

Using this sort of definition is sometimes convenient for a detailed study of hash functions. You can also have collision-resistant hash functions, which possess property 3.

In fact, property 3 implies property 2 implies property 1. (In other words, there is a hierarchy of security properties, each one implying the one above it.) So a hash function that is collision-resistant is also second-preimage resistant and preimage resistant. Note that it does not go the other way: MD5 is an example of a hash function that is preimage resistant (very much so) but is very broken when it comes to collision resistance.

Ultimately, it just depends on whose definition you are using. In this case, I'm essentially summarizing the definitions given in the Handbook of Applied Cryptography.

Answer 2

A one-way function is any function that is hard to invert. A cryptographic hash is hard to invert, and is therefore a member of the set of one-way functions. But that answers only half your question. There are other one-way functions that aren't used as cryptographic hash functions.

The multiplication of two large prime numbers is a one-way function because it is easy to compute but hard to invert, as the inverse involves factoring. When implemented in the RSA algorithm, it yields two related one-way functions that both rely on multiplication: what one can multiply, only multiplication by the other can recover. Because factoring is still hard, neither multiplication function can be easily inverted. The RSA algorithm created what became known as "public key" cryptography, and it's also built on one-way functions.