Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-005 | 17th February 1997 00:00

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


Authors: Moni Naor, Omer Reingold
Publication: 19th February 1997 13:27
Downloads: 3394


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.

ISSN 1433-8092 | Imprint