# Luby-Rackoff theorem confusion

The Luby-Rackoff theorem states that if a round function is a secure pseudorandom function (PRF) then 3 rounds are sufficient to make the block cipher a pseudorandom permutation (PRP).

PRPs are invertible whereas PRFs are not. How come 3 rounds of a PRF will make an invertible block cipher out of a non-invertible function?

• (This is actually a question about the Feistel construction, not the Luby-Rackoff result.) It's not three successive invocations of the PRF, it's three rounds of the Feistel construction, instantiated with the PRF as the round functions. It's not hard to see that any number of Feistel rounds are invertible using the round functions in only the forward direction -- they do not need to be invertible. See Wikipedia for more info on the Feistel construction. – Chris Peikert Aug 12 '14 at 23:44
• Maybe it helps to remind yourself of the fact that Michael Luby and Charles Rackoff analyzed the Feistel cipher construction. Simpler said: The answer can not be found by stricktly looking at PRFs… instead you should be looking closer at Feistel constructions, as they show how 3 rounds of a PRF will make an invertible block cipher out of a non-invertible function. – e-sushi Aug 13 '14 at 17:48
• @e-sushi The first hyperlink does not seem to be working anymore. – hola Sep 28 '20 at 9:03
• @yyyy0000 You might want to check your browser and DNS settings, because that first link — which I have posted in my 2014 comment — is still alive and well. QED: i.stack.imgur.com/xXIDN.jpg (Note that it's a website, not a PDF download) Hope that helps… – e-sushi Sep 29 '20 at 11:04
• @yyyy0000 As an aside, here's a constructive hint: your favorite search engine is your friend. Just search for the title and authors, and you'll quickly find stuff like researchgate.net/publication/… which also offers the PDF download. Users are not search engines, but this one time, I did a quick lookup for your convenience. – e-sushi Sep 29 '20 at 11:10

The proof is loosely as below.

Lets assume a one round Feistel network, where $2n$ bits are divided into $n$ bits each $L_0, R_0$

The encryption is defined as

$L_{1} = R_{0}, \\ R_{1} = L_0 \oplus f(R_0)$

where f is any random function (PRF) and $\oplus$ is XOR operation

Now the cipher text is $L_{2} = R_{1}, R_{2} = L_1$

Decryption is same as encryption circuit as defined above.

The input to decryption is $L_2, R_2$.

So decryption is defined as below

$L_{3} = R_{2} \\ R_{3} = L_{2} \oplus f(R_2)$

Where the plain text should be considered $R_3, L_3$

Now lets substitute from $L_{3} = L_{1}, \\ R_{3} = R_{1} \oplus f(L_1)$

Now lets substitute further to get the plain text is $R_3, L_3$ which is $L_0, R_0$ as shown below $L_{3} = R_{0}, \\ R_{3} = L_0 \oplus f(R_0) \oplus f(R_{0}) ,\\ R_{3} = L_0$

So it does not really matter if $f(R_0)$ is reversible or not. And the same holds good for any number of rounds.

There is also an intuitive explanation here

• Umm... this is how the overall security of a (2 branch, balanced) Feistel scheme works, may be, you can cover a little on how the proof of L-R theorem works. – hola Dec 11 '18 at 12:48