Cryptology ePrint Archive: Report 2000/042

Constructing Pseudo-Random Permutations with a Prescribed Structure

Moni Naor and Omer Reingold

Abstract: We show how to construct pseudo-random permutations 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 {\em fast forward} property, i.e. it is possible to iterate them at a very small cost.

Category / Keywords: secret-key cryptography / Pseudo-random Permutations, Cycles, Block-Ciphers, Involution, Cyclic Permutations

Date: received 11 Aug 2000

Contact author: omer at researc att com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20000811:231142 (All versions of this report)

Short URL: ia.cr/2000/042

Discussion forum: Show discussion | Start new discussion