On the construction of pseudo-random permutations
Moni Naor, Omer Reingold · 1997
Luby and Rackoff [21] showed a method for constructing a pseudo-random permutation from a pseudorandom 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:q Reduce the success probability of the adversary.q Provide a construction of pseudo-random permutations with large input size using pseudo-random functions with small input size.