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 one-way function $f$ is distributionally one-way with the constant polynomial $p:=2$: 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/2,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))$, which bounds the distance below by $1-{\mathbf{Adv}}_{f,\mathcal{A}}^{\mathrm{pr}}(n)$. The advantage is negligible, so it is at most $1/2$ for all sufficiently large $n$.

Notes

• The argument uses only that every efficient inverter fails with probability at least $1/p(n)$ for all sufficiently large $n$, so every weakly one-way function is distributionally one-way with the same $p$ (Weak OWF ⇒ Distributional OWF) — folklore.
• If a one-way permutation $\pi$ on $\{0,1{\}}^n$ exists, a distributionally one-way function need not be weakly one-way: let $f(x,0):=x$ and $f(x,1):=\pi (x)$. Every $y$ has exactly the two preimages $(y,0)$ and $({\pi }^{-1}(y),1)$, so $f$ is inverted with probability $1$; but $y=f(x,b)$ is uniform, a uniform preimage of it is $({\pi }^{-1}(y),1)$ with probability $1/2$, and every efficient $\mathcal{A}$ outputs that preimage with negligible probability, so $f$ is distributionally one-way with $p:=3$ — folklore.
• The converse holds for existence only, through a different function: distributional one-way functions yield one-way functions — IL89.