International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Constructing Pseudo-Random Permutations with a Prescribed Structure

Authors:
Moni Naor
Omer Reingold
Download:
URL: http://eprint.iacr.org/2000/042
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2000-11386,
  title={Constructing Pseudo-Random Permutations with a Prescribed Structure},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Pseudo-random Permutations, Cycles, Block-Ciphers, Involution, Cyclic Permutations},
  url={http://eprint.iacr.org/2000/042},
  note={ omer@researc.att.com 11180 received 11 Aug 2000},
  author={Moni Naor and Omer Reingold},
  year=2000
}