Universal one-way hash function

From CRYPTUTOR

A universal one-way hash function (UOWHF) is a hash function which achieves a "selective" version of collision-resistance.

[edit]

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 universal one-way 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$ :

UOWHF Collision Experiment:

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