On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited
Moni Naor and Omer Reingold
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:
, gzipped Postscript
1. Reduce the success probability of the adversary.
2. Provide a construction of pseudo-random permutations with large input-length
using pseudo-random functions with small input-length.
Related On-Line Papers:
Moni Naor and Omer Reingold, The NR Mode of Operation, Postscript,
Matt Blaze, Joan Feigenbaum and Moni Naor. A Formal Treatment of
Remotely-Keyed Encryption, Eurocrypt 98. Abstract
Moni Naor and Omer Reingold, Constructing Pseudo-Random Permutations
with a Prescribed Structure, J. of Cryptology, vol 14, 2001.
Back to On-Line Publications