PRG ⇒ OWF

Fully-black-box reduction · standard model · folklore

Statement

Every PRG $G:\{0,1{\}}^n\to \{0,1{\}}^m$ with $m>n$ is a one-way function: an efficient inverter for $G$ with success probability $\epsilon$ yields an efficient PRG distinguisher with advantage at least $(1-2^{n-m})\epsilon \ge \epsilon /2$ — folklore.

Sketch

Given an inverter $\mathcal{A}$, the distinguisher $D(y)$ runs $\hat{x}\leftarrow \mathcal{A}(y)$ and outputs $1$ iff $G(\hat{x})=y$. On $y=G(s)$ it outputs $1$ with probability $\epsilon$; on uniform $y$ with probability at most $2^{n-m}\epsilon$, since each $y$ in the image of $G$ has probability $2^{-m}\le 2^{n-m}{\mathrm{Pr}}_s[G(s)=y]$.

Notes

• Conversely, every one-way function yields a PRG (OWF ⇒ PRG) — HILL99.