Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Most of the papers on block cipher constructions, especially the ones which discuss constructing block ciphers of arbitrary lengths or small domains, the techniques are designed based on building a PRP from a PRF. The ones that are based on Luby-Rackoff etc.
Why is it that the input message first to be processed by a pseudorandom function and then followed by a pseudorandom permutation? Why cannot we construct PRP straight from input message?
If you applied a PRF directly to the message to obtain cipher-text, you would not have the guarantee that you could actually decrypt the message.
Suppose the PRF maps $n$ bit inputs to some $m$ bit output.
The mental model of a PRF is as follows. You have have a gnome in a black box. When you hand him a string from the input space, he flips a coin $m$ times and outputs the result of these flips concatenated together. He then records this in his notebook so that if you pass the same $n$-bit input to him again, he can give you the same output.
If you think about this model carefully, you'll realise that there's actually nothing to stop two inputs mapping to the same output. You just have to be lucky enough for a collision to occur. Due to the birthday paradox, this happens more often than you'd expect and there will typical be quite a lot of collisions.
Thus, if we try to encrypt our message directly with a PRF, there's no guarantee we'd be able to invert it!
A PRP is a PRF with the additional restriction that for every input value maps to precisely one output value and that every output value maps to precisely one input. With a PRP we're guaranteed to have an invertible function, which is precisely what we need to construct a block cipher.
In the PRP mental model, the gnome has a list of all possible output strings of length $m$. Every time he is passed an input he hasn't seen before, he selects an item from the list of output strings at random. He then removes this item from the list (so it can't be re-used) and writes in his notebook the input string and which output string he mapped it to. If he ever sees the same input again, he can then give the output he's recorded in his note book.
We can see that this construction is quite a bit more complex than the PRF set-up. The Luby-Rackoff construction is so neat because it gives us a nice way to convert a secure PRF in to secure PRP. There is a similar result for going to a PRF from a PRG, which is called the Goldreich-Goldwasser-Micali construction.
The end result being if you can build a secure pseudo random number generator you can also build a secure block-cipher. This is a neat result, which is why it's so often referred to in the cryptographic literature.
