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?

  • 13
    $\begingroup$ (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. $\endgroup$ Commented Aug 12, 2014 at 23:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – e-sushi
    Commented Aug 13, 2014 at 17:48
  • $\begingroup$ @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.sstatic.net/xXIDN.jpg (Note that it's a website, not a PDF download) Hope that helps… $\endgroup$
    – e-sushi
    Commented Sep 29, 2020 at 11:04
  • $\begingroup$ @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. $\endgroup$
    – e-sushi
    Commented Sep 29, 2020 at 11:10
  • $\begingroup$ Does this help? ei.ruhr-uni-bochum.de/media/ei/lehrmaterialien/… $\endgroup$
    – hola
    Commented May 29, 2021 at 17:41

1 Answer 1


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

  • $\begingroup$ 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. $\endgroup$
    – hola
    Commented Dec 11, 2018 at 12:48

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.