Distributional OWF ⇒ OWF (Impagliazzo–Luby)

Fully-black-box reduction · standard model · IL89 · security loss: polynomial: the one-way function’s input length is polynomial in n and p(n), and the distributional inverter for f calls an inverter for it a number of times polynomial in n, p(n) and the inverse of its success probability

Statement

If a distributionally one-way function exists, then a one-way function exists — IL89. Contrapositively, if no one-way function exists, then for every polynomial-time computable $f$ and every polynomial $p$ there is an efficient $\mathcal{A}$ such that, for infinitely many $n$,

$$\Delta ((x,f(x)),(\mathcal{A}(f(x)),f(x)))<1/p(n),x\stackrel{\$}{\leftarrow }\{0,1{\}}^n,$$

with $\Delta$ the statistical distance — IL89.

Notes

• The one-way function appends to $f(x)$ a pairwise-independent hash of $x$, truncated to a length that is part of its input. An inverter for it that succeeds with probability close to $1$ yields a distributional inverter for $f$, so it is weakly one-way, and Yao’s amplification makes it one-way — IL89, Yao82a.
• The converse holds with the same function: every one-way function is distributionally one-way — folklore.
• IL89 apply the contrapositive to functions built from a scheme’s algorithms to show that secure symmetric-key encryption, commitment schemes and identification schemes imply one-way functions — IL89.