3
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.