Constructing Pseudo-Random Permutations with a Prescribed
Structure
Moni Naor and Omer Reingold
Abstract:
We show how to construct pseudo-random permutations (see link
for background) that satisfy a certain cycle restriction, for example that
the permutation be cyclic (consisting of one cycle containing all
the elements) or an involution (a self-inverse permutation) with
no fixed points. The construction can be based on any (unrestricted)
pseudo-random permutation. The resulting permutations
are defined succinctly and their evaluation at a given point is efficient.
Furthermore, they enjoy a fast forward property, i.e.
it is possible to iterate them at a very small cost.
Postscript , gzipped
Postscript.
Slides: ppt
Related On-Line Papers:
Moni Naor and Omer Reingold, On the construction of pseudo-random
permutations: Luby-Rackoff revisited, J. of Cryptology, vol 12,
1999, pp. 29-66.
Abstract,
Postscript,
gzipped
Postscript .
Back to On-Line Publications
Back Home