On the Construction of PseudoRandom Permutations: LubyRackoff Revisited
Moni Naor and Omer Reingold
Abstract:
Luby and Rackoff showed a method for constructing a pseudorandom 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 pseudorandom 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 pairwise 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 pseudorandom permutations with large inputlength
using pseudorandom functions with small inputlength.
Postscript
, gzipped Postscript
Related OnLine Papers:

Moni Naor and Omer Reingold, The NR Mode of Operation, Postscript,
gzipped
Postscript

Matt Blaze, Joan Feigenbaum and Moni Naor. A Formal Treatment of
RemotelyKeyed Encryption, Eurocrypt 98. Abstract
,
Postscript,
gzipped
Postscript

Moni Naor and Omer Reingold, Constructing PseudoRandom Permutations
with a Prescribed Structure, J. of Cryptology, vol 14, 2001.
Abstract,
Postscript,
gzipped
Postscript
Back to OnLine Publications
Back Home