PRP ⇒ iPRF (large domains)

Fully-black-box reduction · standard model · via Switching Lemma · folklore · security loss: $O(q^2/|\mathcal{D}|)$ for $q$ queries, per the switching lemma

Statement

A PRP $(\mathsf{KeyGen},\mathsf{Eval},\mathsf{Invert})$ over a domain $\mathcal{D}$ with $|\mathcal{D}|$ superpolynomial in $\lambda$ is an invertible PRF for the traditional (forward-oracle) game ${\mathbf{G}}^{\mathrm{prf}}$, with inversion algorithm $y\mapsto \{\mathsf{Invert}(k,y)\}$: for every $q$-query $\mathcal{A}$ the PRF advantage is at most the PRP advantage plus the $O(q^2/|\mathcal{D}|)$ term of the Switching Lemma, as in PRP ⇒ PRF — folklore. Strong security under ${\mathbf{G}}^{\mathrm{iprf}}$, where $\mathcal{A}$ also queries the inversion oracle, fails for every permutation, since $\{\mathsf{Invert}(k,y)\}$ is never empty while a random function’s preimage set is empty with constant probability — folklore.

Sketch

A permutation is an iPRF with singleton preimage sets and perfect correctness. Against forward queries a random permutation is statistically within $O(q^2/|\mathcal{D}|)$ of a random function, so PRP security transfers to ${\mathbf{G}}^{\mathrm{prf}}$ with birthday loss.