Weak OWF ⇒ Distributional OWF

Fully-black-box reduction · standard model · folklore · security loss: none: the function is unchanged, and an algorithm whose output pair is at statistical distance Δ from (x, f(x)) inverts f with probability at least 1 − Δ

Statement

Every weakly one-way function $f$ is distributionally one-way with the same polynomial $p$: if every efficient inverter fails with probability at least $1/p(n)$ for all sufficiently large $n$, then for all efficient $\mathcal{A}$ and all sufficiently large $n$,

$$\Delta ((x,f(x)),(\mathcal{A}(f(x)),f(x)))\ge 1-{\mathbf{Adv}}_{f,\mathcal{A}}^{\mathrm{pr}}(n)\ge 1/p(n),x\stackrel{\$}{\leftarrow }\{0,1{\}}^n,$$

with $\Delta$ the statistical distance — folklore.

Sketch

The event that the first component is a preimage of the second has probability $1$ under $(x,f(x))$ and probability ${\mathbf{Adv}}_{f,\mathcal{A}}^{\mathrm{pr}}(n)$ under $(\mathcal{A}(f(x)),f(x))$.