TR97-005 Authors: Moni Naor, Omer Reingold

Publication: 19th February 1997 13:27

Downloads: 2657

Keywords:

Luby and Rackoff 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:

1. Reduce the success probability of the adversary.

2. Provide a construction of pseudo-random permutations with large

input size using pseudo-random functions with small input size.

3. Provide a construction of a pseudo-random permutation

using a single pseudo-random function.