PRF ⇒ Strong PRP

Fully-black-box reduction · standard model · LR88 · security loss: sum of the round PRF advantages plus additive $O(q^2/2^n)$ for $q$ queries

Statement

If $\mathsf{PRF}$ is a PRF on $\{0,1{\}}^n$ with $n=\omega (\log \lambda )$, the four-round Feistel network with independently keyed round functions is a strong PRP on $\{0,1{\}}^{2n}$, secure against distinguishers that also query the inverse — LR88.

Sketch

The round functions are replaced by independent random functions one at a time, each hop a PRF distinguisher. With random round functions, the outer rounds randomize the inputs of the inner rounds for forward and inverse queries alike, so the network is indistinguishable from a random permutation except with probability $O(q^2/2^n)$ — LR88.

Notes

• Three rounds give a PRP that is not strong: PRF ⇒ PRP — LR88.