Weak OWF ⇒ OWF (Yao)

Fully-black-box reduction · standard model · Yao82a · security loss: polynomial: the input grows from n to n²p(n) bits, and the inverter for f makes polynomially many calls to the inverter for F

Statement

Let $f$ be a weak one-way function on $\{0,1{\}}^n$: there is a polynomial $p$ such that every efficient inverter fails on a uniform $x\stackrel{\$}{\leftarrow }\{0,1{\}}^n$ with probability at least $1/p(n)$, for all sufficiently large $n$. Then the direct product

$$F(x_1,\dots ,x_t):=(f(x_1),\dots ,f(x_t)),t:=n\cdot p(n),$$

on independent uniform blocks $x_i\stackrel{\$}{\leftarrow }\{0,1{\}}^n$, is a one-way function — Yao82a.

Sketch

The inverter for $f$ plants its challenge $y$ at a uniform position $i\in [t]$ among $t-1$ honestly sampled blocks $f(x_j)$, runs an inverter $\mathcal{A}$ for $F$ that succeeds with probability $\epsilon$, and outputs the $i$-th block of a successful answer, repeating $O(tn/\epsilon )$ times. Call $y$ good if one trial succeeds with probability at least $\epsilon /(2t)$: if more than a $1/(2p)$ fraction of inputs map to bad $y$, then all $t$ blocks of a uniform input to $F$ are good with probability at most $(1-1/(2p){)}^t\le e^{-n/2}$, and a union bound over the bad block bounds $\mathcal{A}$‘s success elsewhere by $\epsilon /2$, so $\epsilon \le 2e^{-n/2}$. Otherwise the repeated trials invert $f$ on all but a $1/(2p)+e^{-n}$ fraction of inputs, contradicting weak one-wayness — Gol01.

Notes

• Every one-way function is weakly one-way — folklore; with this reduction, weak one-way functions exist iff one-way functions do.
• The amplification is not security preserving: the security of $F$ on $N$-bit inputs rests on that of $f$ on $n$-bit inputs with $N=n^{2}p(n)$. For a weak one-way permutation, iterating the permutation along a random walk on an expander graph replaces the independent blocks and keeps the input length linear in $n$ — GILVZ90.