Is 3 rounds of Feistel enough for making a PRP?

Question

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?

Answer 1

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.