OWP ⇒ UOWHF (Naor–Yung)

Fully-black-box reduction · standard model · NY89 · security loss: none: an adversary finding a target collision with probability ε inverts the permutation with probability ε(1 - 2^{-n})

Statement

Let $\pi$ be a one-way permutation on $\{0,1{\}}^n$, identified with ${\mathbb{F}}_{2^n}$, and let $\mathrm{chop}$ delete the last bit of an $n$-bit string. The family

$${\mathsf{H}}_{a,b}(x):=\mathrm{chop}(a\cdot \pi (x)+b),(a,b)\stackrel{\$}{\leftarrow }{\mathbb{F}}_{2^n}^{\ast }\times {\mathbb{F}}_{2^n},$$

maps $n$ bits to $n-1$ bits and is a universal one-way hash function — NY89. Composing independently keyed one-bit-compressing families compresses by any polynomial number of bits — NY89.

Sketch

Let $\mathcal{A}$ name the target $x$ before the key, and let the reduction hold a challenge $y=\pi (z)$ for uniform $z$. It samples $w\stackrel{\$}{\leftarrow }{\mathbb{F}}_{2^n}$ and solves for the unique affine map $g(u)=au+b$ with $g(\pi (x))=w$ and $g(y)=w+e_n$, where $e_n$ is the last unit vector; when $y\ne \pi (x)$ this gives $a=e_n/(y+\pi (x))\ne 0$, and since $y$ is uniform and independent of $\mathcal{A}$‘s view, $(a,b)$ is uniform. A collision $\hat{x}\ne x$ satisfies $g(\pi (\hat{x}))\in \{w,w+e_n\}$, and injectivity of $\pi$ and $g$ excludes $w$, so $\pi (\hat{x})=y$.

Notes

• Any pairwise-independent family of permutations that can be sampled uniformly conditioned on two input–output pairs can replace the affine maps over ${\mathbb{F}}_{2^n}$ — NY89.
• Efficiency: one evaluation of $\pi$ per bit of compression, so compressing $n$ bits to $n-k$ costs $k$ evaluations and a key of $2k$ field elements. No fully-black-box construction from a one-way permutation of security $S$ compresses by $k$ bits with $o(k/\log S)$ queries — GT00.
• One-way functions suffice: OWF ⇒ UOWHF — Rom90.