sPRP ⇒ PRP

Fully-black-box reduction · standard model · folklore · security loss: tight: the same adversary has the same advantage in both games

Statement

Every strongly pseudorandom permutation $\mathsf{PRP}$ is pseudorandom: for every PRP adversary $\mathcal{A}$, ${\mathbf{Adv}}_{\mathsf{PRP},\mathcal{A}}^{\mathrm{prp}}(\lambda )={\mathbf{Adv}}_{\mathsf{PRP},\mathcal{A}}^{\mathrm{sprp}}(\lambda )$, where on the right $\mathcal{A}$ runs in the sPRP game and never queries ${\mathcal{O}}_b^{-1}$ — folklore.

Sketch

The reduction is the identity on adversaries: it forwards the PRP distinguisher’s queries to the forward oracle, ignores the inverse oracle, and outputs its guess; both games give the distinguisher the same view.