TDP ⇒ OWF

Fully-black-box reduction · standard model · folklore · security loss: none: the reduction preserves the inverter’s advantage

Statement

A trapdoor permutation family $(\mathsf{Gen},\mathsf{Eval},\mathsf{Invert})$ yields a one-way function $g(r,x):=(f,\mathsf{Eval}(f,x))$, where $(f,\mathsf{td}):=\mathsf{Gen}(1^{\lambda };r)$ — folklore.

Sketch

$g$ discards $\mathsf{td}$. The reduction forwards its challenge $(f,y)$ to a $g$-inverter and returns the $x$ component of the answer, which is the unique preimage of $y$ under the bijection $\mathsf{Eval}(f,\cdot )$.