Collision resistant hash function

From CRYPTUTOR

(Redirected from CRHF)

A collision resistant hash function (CRHF) is a hash function for which it is infeasible to find any collision.

Definition

Let $m$ and $h$ be polynomials, and let $\mathcal{H}_n = \{ H_k \}_{k \in \{0,1\}^n}$ be a collection of functions from $m (n)$ bits to $h (n)$ bits, indexed by seeds $k$ . We say that $\mathcal{H}_n$ is a collision resistant hash function if it has the following properties:

Efficiency: $H k (m)$ can be computed in polynomial time in the security parameter $n$ .
Compression: $h (n) < m (n)$ for all $n$ .
Collision-resistance: For all non-uniform PPT (polynomial in the security parameter $n$ ) adversaries $A$ , the probability that $A$ succeeds in the following experiment is negligible in $n$ :

CRHF Collision Experiment:

We choose a random seed $k \gets \{0,1\}^n$ and give it to the adversary.
$A$ outputs two different strings $x\ne y \in \{0,1\}^{m(n)}$ .
We say that $A$ succeeds if $H k (x) = H k (y)$ .