Paper 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.

Metadata
Available format(s)
PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Pseudo-random PermutationsCyclesBlock-CiphersInvolutionCyclic Permutations
Contact author(s)
omer @ researc att com
History
2000-08-11: received
Short URL
https://ia.cr/2000/042
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2000/042,
      author = {Moni Naor and Omer Reingold},
      title = {Constructing Pseudo-Random Permutations with a Prescribed Structure},
      howpublished = {Cryptology {ePrint} Archive, Paper 2000/042},
      year = {2000},
      url = {https://eprint.iacr.org/2000/042}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.