Constructing Pseudo-Random Permutations with a Prescribed Structure

 Moni Naor and Omer Reingold


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