PRF ⇒ 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 three-round Feistel network with independently keyed round functions $\mathsf{Eval}(k_1,\cdot ),\mathsf{Eval}(k_2,\cdot ),\mathsf{Eval}(k_3,\cdot )$ is a PRP on $\{0,1{\}}^{2n}$, and the four-round network is a strong PRP, secure given the inverse oracle as well — LR88. Two Feistel rounds between initial and final pairwise-independent permutations already give a strong PRP, with a simpler proof — NR99.

Sketch

On input $(L_0,R_0)\in \{0,1{\}}^n\times \{0,1{\}}^n$, round $i$ sets $(L_i,R_i)\leftarrow (R_{i-1},L_{i-1}\oplus \mathsf{Eval}(k_i,R_{i-1}))$, a permutation whatever the round function, and $\mathsf{Invert}$ runs the rounds backwards. Hybrids replace each round function by a truly random one, and the three-round random-function core is indistinguishable from a random permutation up to a birthday bound.

Notes

• The birthday term $O(q^2/2^n)$ makes the bound negligible only when $2^n$ is superpolynomial in $\lambda$ — LR88.
• Efficiency: each round evaluates the PRF once on $n$ bits, so a $2n$-bit block costs three PRF calls, or four for a strong PRP; with pairwise-independent permutations in place of the outer rounds, two PRF calls suffice — NR99.