PRP ⇒ PRF

Fully-black-box reduction · standard model · via Switching Lemma · IR89 · security loss: ${\mathbf{Adv}}^{\mathrm{prf}}\le {\mathbf{Adv}}^{\mathrm{prp}}+q(q-1)/(2|\mathcal{D}|)$ for $q$ queries (birthday bound)

Statement

A PRP over a domain $\mathcal{D}$ with $|\mathcal{D}|$ superpolynomial in $\lambda$ is a PRF with $\mathsf{Eval}$ unchanged: for every $q$-query $\mathcal{A}$, ${\mathbf{Adv}}_{\mathsf{PRP},\mathcal{A}}^{\mathrm{prf}}(\lambda )\le {\mathbf{Adv}}_{\mathsf{PRP},\mathcal{A}}^{\mathrm{prp}}(\lambda )+O(q^2/|\mathcal{D}|)$ by the Switching Lemma, and for efficient $\mathcal{A}$ the additive term is negligible — IR89.

Sketch

Sampled lazily, a random function on $\mathcal{D}$ answers $q$ distinct queries as a random permutation does until two of its outputs collide, which happens with probability at most $q(q-1)/(2|\mathcal{D}|)$; so any PRF distinguisher is a PRP distinguisher up to that additive term.

Notes

• The switching lemma has a game-playing proof, which corrects a conditioning flaw in the standard proof — BR06.
• For streaming distinguishers with $m$ bits of memory the bound is $O(mq\log q/|\mathcal{D}|)$, tight up to polylogarithmic factors — Din20.