Lossy TDF ⇒ Injective TDF

Fully-black-box reduction · standard model · PW08 · security loss: additive 2^{-k} for lossiness k: an inverter with success ε distinguishes the modes with advantage ε − 2^{-k}

Statement

The injective mode of a lossy trapdoor function whose lossy mode loses $k=\omega (\log \lambda )$ bits is an injective trapdoor function — PW08.

Sketch

Given an index of either mode, sample $x$ uniformly, run the inverter on $f(x)$ and output $1$ iff it returns $x$. In the injective mode this happens with the inverter’s success probability $\epsilon$. In the lossy mode $f(x)$ takes at most $2^{n-k}$ values, so $x$ has average min-entropy $k$ given $f(x)$ and no algorithm returns it with probability above $2^{-k}$ — PW08.