8
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ella Rose
    Commented May 16, 2016 at 15:19
  • $\begingroup$ I thought it was 4 rounds... $\endgroup$
    – Richie Frame
    Commented May 16, 2016 at 15:48
  • $\begingroup$ @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 :) $\endgroup$
    – Kaustubh
    Commented May 16, 2016 at 16:26
  • $\begingroup$ @RichieFrame just rechecked, it's 3 rounds atleast $\endgroup$
    – Kaustubh
    Commented May 16, 2016 at 16:27
  • 2
    $\begingroup$ @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'$ $\endgroup$
    – poncho
    Commented May 16, 2016 at 16:33

2 Answers 2

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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). $\endgroup$
    – Aleph
    Commented May 16, 2016 at 20:00
  • $\begingroup$ @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. $\endgroup$
    – Ella Rose
    Commented May 16, 2016 at 21:24
  • $\begingroup$ 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. $\endgroup$
    – Aleph
    Commented May 16, 2016 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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