[Download postscript version]

Requirements for Traditional Hash Functions

This review is based on the ``Handbook of Applied Cryptography'' [10].

• A hash function is a function h which has, as a minimum, the following two properties:
  1. Compression: h maps an input x of arbitrary finite length, to an output $h(x)$ of fixed bit length $n$.
  2. Ease of computation: given $h$ and an input $x$, $h(x)$ is easy to compute.
• Three most desired properties:
  1. Preimage resistance: for any pre-specified output $y$, it is computationally infeasible to find the input $x$ such that $h(x)\; =\; y$.
  2. 2nd-preimage resistance: given any input $x$, it is computationally infeasible to find an input $x\text{'}$ such that $h(x\text{'})\; =\; h(x)$.
  3. Collision resistance: it is computationally infeasible to find any two distinct inputs $x,\; x\text{'}$ which hash to the same output, $h(x)\; =\; h(x\text{'})$.
• A one-way hash function is a hash function h with two additional properties: pre-image resistance and 2nd-preimage resistance. A collision resistant hash function is a hash function h with the additional property of collision resistance.