On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited

Abstract Luby and Rackoff [27] showed a method for constructing a pseudo-random permutation from a pseudo-random function. The method is based on composing four (or three for weakened security) so called Feistel permutations, each of which requires the evaluation of a pseudo-random function. We reduce somewhat the complexity of the construction and simplify its proof of security by showing that two Feistel permutations are sufficient together with initial and final pair-wise independent permutations. The revised construction and proof provide a framework in which similar constructions may be brought up and their security can be easily proved. We demonstrate this by presenting some additional adjustments of the construction that achieve the following: ffl Reduce the success probability of the adversary. ffl Provide a construction of pseudo-random permutations with large input size using pseudorandom functions with small input size