CRHF ⇒ Weak OWF

Fully-black-box reduction · standard model · folklore · security loss: additive 2^{-(n-m)}: an inverter with success ε gives a collision finder with success at least ε − 2^{-(n-m)}

Statement

Let $\mathsf{H}:\mathcal{K}\times \{0,1{\}}^n\to \{0,1{\}}^m$ with $m<n$ be a collision-resistant family. Then $f(k,x):=(k,\mathsf{H}(k,x))$ is weakly one-way: an inverter succeeding with probability $\epsilon$ yields a collision finder succeeding with probability at least $\epsilon -2^{m-n}\ge \epsilon -1/2$, so every efficient inverter succeeds with probability at most $1/2+\mathrm{negl}(\lambda )$ — folklore. If $n-m=\omega (\log \lambda )$, the same bound makes $f$ one-way.

Sketch

The collision finder samples $x\stackrel{\$}{\leftarrow }\{0,1{\}}^n$, runs the inverter on $(k,\mathsf{H}(k,x))$, and outputs $(x,\hat{x})$. The inverter’s view depends on $x$ only through $\mathsf{H}(k,x)$, so given a successful answer, $\hat{x}=x$ with probability $1/|{\mathsf{H}}_k^{-1}(\mathsf{H}(k,x))|$, whose expectation over $x$ is the number of images divided by $2^n$, at most $2^{m-n}$.

Notes

• One bit of compression does not make $f$ one-way. For a collision-resistant ${\mathsf{H}}_k^{\prime }:\{0,1{\}}^n\to \{0,1{\}}^{n-2}$, let ${\mathsf{H}}_k(00u):=0u$ for $u\in \{0,1{\}}^{n-2}$ and ${\mathsf{H}}_k(x):=1\Vert {\mathsf{H}}_k^{\prime }(x)$ otherwise. Then ${\mathsf{H}}_k$ compresses by one bit, and every collision of ${\mathsf{H}}_k$ is a collision of ${\mathsf{H}}_k^{\prime }$, because the first branch is injective and the two branches have disjoint ranges; yet $f$ is inverted on every input beginning with $00$, a quarter of them — standard.
• One-way functions follow from any collision-resistant family, by amplification: Weak OWF ⇒ OWF — Yao82a. Alternatively, Merkle–Damgård iteration gives a collision-resistant family with $n-m=\omega (\log \lambda )$ — Dam89 — and then $f$ itself is one-way.
• Bounds relating preimage, second-preimage and collision resistance as functions of the compression are in RS04.
• The converse has no relativizing proof: No relativizing reduction from OWP to CRHF — Sim98.