10
$\begingroup$

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?

$\endgroup$
  • 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$ – Chris Peikert Aug 12 '14 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 Aug 13 '14 at 17:48
10
$\begingroup$

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

$\endgroup$
  • $\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$ – xxx--- Dec 11 '18 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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