# 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?

• Presumably you can just apply the PRF/PRP lemma? – Squeamish Ossifrage Jun 19 '19 at 12:48
• For what it's worth, Piret proved this directly. – Samuel Neves Jun 19 '19 at 17:41

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.