OWP ⇒ OWF

Fully-black-box reduction · standard model · folklore

Statement

Every one-way permutation $\pi$ whose input distribution $X$ is uniform on $\mathcal{D}$ is a one-way function with a trivial key and $\mathcal{R}=\mathcal{D}$: the one-wayness game, which samples $x\stackrel{\$}{\leftarrow }\mathcal{D}$, is then the permutation’s inversion game, so an inverter for the function is an inverter for the permutation with the same advantage — folklore.

Notes

• For $X$ sampled by an efficient $S$ from uniform coins, $r\mapsto \pi (S(r))$ is a one-way function: an $r^{\prime }$ with $\pi (S(r^{\prime }))=y$ gives the preimage $S(r^{\prime })$ of $y$ under $\pi$ — folklore.
• Collision resistance does not follow: no relativizing construction of a collision-resistant hash function from a one-way permutation exists (No relativizing reduction from OWP to CRHF) — Sim98.