# Need for 3 rounds in Luby Rackoff theorem

I get that using Feistel network we can create a secure PRP from a secure PRF (in 3 rounds according to theorem).

My question is why not just 2 rounds of Feistel network is sufficient. Is it that the output is random enough compared to a truly random string before 3 rounds?

• At the very least because of diffusion. First, the right influences the left half, then the left influences the right half. After two rounds, the right half has not influenced itself, and the left half has not influenced itself. – Ella Rose May 16 '16 at 15:19
• I thought it was 4 rounds... – Richie Frame May 16 '16 at 15:48
• @EllaRose I don't know much about diffusion, but your comment helps out,.. Btw add it as an answer and I'll accept it if nothing more is answered. Btw could you perhaps give me any helpful links on diffusion. Thanks :) – Kaustubh May 16 '16 at 16:26
• @RichieFrame just rechecked, it's 3 rounds atleast – Kaustubh May 16 '16 at 16:27
• @EllaRose: actually, in the 2 round structure, the right side does influence itself (via the left side). You're correct in that the left side doesn't influence itself; hence if we encrypt both $(R, L)$ and $(R, L')$, the result will be the ciphertexts $(A, B)$ and $(C, D)$ with $B \oplus D = L \oplus L'$ – poncho May 16 '16 at 16:33

The simple answer is that fewer than 3 rounds can be easily distinguished from a random permutation. The 2-round Luby-Rackoff cipher on $2n$ bits, using random functions $f_i$ mapping $n$ bits to $n$ bits, consists of $$F(L, R) = (A, B),$$ where $A = L \oplus f_1(R)$ and $B = R \oplus f_2(L \oplus f_1(R))$.

Now consider an attacker that wants to distinguish $F$ from a random permutation. First they send some arbitrary $(L_1, R_1)$ to the oracle, and get back $(A_1, B_1)$.

Next they send $(L_2, R_1)$, which results in $(A_2, B_2)$. Verifying that $A_1 \oplus A_2$ = $L_1 \oplus f_1(R_1) \oplus L_2 \oplus f_1(R_1)$ = $L_1 \oplus L_2$, the attacker is now pretty sure this is the Luby-Rackoff cipher.

What happens at 3 rounds is that no such distinguisher (querying only in the forward direction, of course!) is now possible. The proof relies on showing that collisions on the internal variables $A_i, B_i$ are necessary to mount any distinguisher, and then shows that those collisions are rare, in that you need approximately $2^{n/2}$ oracle queries to obtain one.

It's required for diffusion and achieving the avalanche effect.

The concept of diffusion and the avalanche effect basically means that each input bit should influence each output bit evenly. Changing one input bit should flip, on average, half the output bits.

Due to the nature of the Feistel construction, how it is split up into halves, only one side influences the other at a time.

• After one round, the right has influenced the left
• After two rounds, the left has influenced the right
• Since the right has influenced the left, the right has now influenced the right too

After just two rounds, the left block has not influenced itself.

• After three rounds, the right has influenced the left again
• After this point, both blocks have been influenced by the other and themselves

Note that achieving full diffusion in the Feistel network is going to require that the prf used on the block provides appropriate diffusion as well.

• Although correct, some more details on the actual proof would be nice. This answer shows that 2 rounds are definitely not going to be enough, but it doesn't show why 3 rounds are enough (but maybe that's beyond what the OP asked). – Aleph May 16 '16 at 20:00
• @Aleph Feel free to suggest any additions/modifications via edits! Or incorporate the information into another answer entirely. I would add more to my answer but I'm not sure what exactly to add. – Ella Rose May 16 '16 at 21:24
• It's been too long since I read that paper, I don't remember much at all :). If anyone has recently read it, that would be welcome. – Aleph May 16 '16 at 21:37