# Is 3 rounds of Feistel enough for making a PRP?

I know that one round of Feistel is not enough for making a PRP (Pseudo Random Permutation). I am also aware that two rounds are not enough. How about three rounds of Feistel?

I did a lot of reading on this topic, but it has not been helpful. For example, here they say that because of the Luby-Rackoff theorem, we have a PRP after three rounds, but here it says that it is not enough.

Which is it?

• You misread the text you linked. 3 rounds is enough for a PRP, but you need 4 rounds for a strong PRP. Feb 14, 2017 at 19:11

Wel'll consider a symmetric Feistel cipher with $$n$$-bit block using ideal independent random functions at each round.

Making it computationally indistinguishable from a random permutation requires some number of rounds depending on the attack model; and on if we are content with asymptotic security for $$O(2^{n/2})$$ work, or want asymptotic security with more work, or want security for a prescribed small $$n$$.

Classical results for asymptotic security with $$O(2^{n/2})$$ work:

• under random known plaintext, we need 2 rounds;
• under chosen plaintext (that is, assuming an encryption oracle, the criteria for a so-called weak PRP), we need 3 rounds; see the famous work of Michael Luby and Charles Rackoff, How to Construct Pseudo-random Permutations from Pseudo-random Functions (in SIAM Journal on Computing Vol. 17, No. 2, 1988, initially presented at Crypto 1985);
• under chosen plaintext and ciphertext (that is, additionally assuming a decryption oracle, the criteria for a so-called strong PRP), we need 4 rounds; for a proof that 3 rounds are not enough, see this answer.

These classical results are nice, and relatively easy to establish, but not directly applied in common practice. First, $$O(2^{n/2})$$ suggests that for 128-bit security (the current baseline), we'd need a 256-bit block cipher (which is uncommon: 128-bit is mainstream, 64-bit used to be). Also, ideal independent random functions at each round is assumed, but actual round functions are quite far from that.

Things are more complex (and more rounds are needed) for asymptotic security with more work; see Jacques Patarin's Security of Random Feistel Schemes with 5 or More Rounds in proceedings of Crypto 2004, or his earlier Luby-Rackoff: 7 Rounds are Enough for $$2^{n(1−\epsilon)}$$ Security, in proceedings of Crypto 2003.

Even more rounds are needed for prescribed small $$n$$, and to my knowledge we only have heuristics.

• I'd rephrase the "chosen ciphertext" variant to emphasize that the attacker has access to both an encryption oracle and a decryption oracle. Feb 14, 2017 at 19:20
• You can drop the $O(\cdot)$; even Luby and Rackoff back in the day provided a concrete bound $Adv_{q} \le 2\binom{q}{2}/2^n \le q^2/2^n$. Feb 15, 2017 at 20:59
• @Samuel Neves: I do see that the Luby/Rackoff proof is quantitative (which is remarkable for 1988), but I do not feel confident enough with that formalism to make the necessary change to my own answer. Fell free to make that, or any other improvement! I made this answer a CW.
– fgrieu
Feb 15, 2017 at 23:05
• Link to the later improvement is broken. Apr 26, 2020 at 3:35
• @Daniel-耶稣活着: I revised the bibliography on Jacques Patarin's articles. Those I formerly linked to are likely preprints, and available there and there thanks to archive.org
– fgrieu
Apr 26, 2020 at 6:53