PRP vs PRF for the F-function of a Feistel network A Feistel network is generally defined with a PRF for its F-function, but PRPs have been used as well. What are the theoretical cryptographic implications of using a PRP instead of a PRF? Does it impact Luby and Rackoff's observation regarding 3 and 4-round Feistel networks with ideal F-functions?
Does it impact Luby and Rackoff's observation regarding 3 and 4-round Feistel networks with ideal F-functions?


No.


  What are the theoretical cryptographic implications of using a PRP instead of a PRF?


We have a bound for the security of Luby-Rackoff based on the PRF-Security of F.
We have a bound on the PRF-security of a PRP ("PRP/PRF-Switching-Lemma").
We can simply plug one into the other to get our answer!

So, first the switching lemma:


  Let $E:\mathbb K\times \mathbb X\to\mathbb X$ be a family of permutations and $N:=|\mathbb X$|. Further let $\mathcal A$ be an efficient adversary against the PRF-security of $E$ making $q$ queries. Then there exists an adversary $\mathcal B$ such that $$\mathbf{Adv}^{\text{PRF}}_E(\mathcal A)\leq \mathbf{Adv}_E^{\text{PRP}}(\mathcal B)+\frac{q^2}{2N}.$$


Now the Luby-Rackoff-Bound (for three rounds):


  Let $F:\mathbb K\times \mathbb X\to\mathbb X$ be a family of functions with $N:=|\mathbb X|$. Further let $\mathcal A$ be an efficient adversary against the PRP-security of $\operatorname{LR}(F)$ making $q$ queries, then there exists an adversary $\mathcal B$ such that
  $$\mathbf{Adv}^{\text{PRP}}_{\operatorname{LR}(F)}(\mathcal A)\leq 3\cdot \mathbf{Adv}_{F}^{\text{PRF}}(\mathcal B)+\frac{q^2}{N}+\frac{q^2}{N^2}.$$


And now finally the combined bound:

$$\mathbf{Adv}^{\text{PRP}}_{\operatorname{LR}(E)}(\mathcal A)\leq 3\cdot \mathbf{Adv}^{\text{PRP}}_E(\mathcal B)+\frac{3q^2}{2N}+\frac{q^2}{N}+\frac{q^2}{N^2}$$

So as you can see, nothing substantially changed here.

The switching lemma and the luby-rackhoff bound can eg be found in the Boneh-Shoup book.