#

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