Paper 1996/011

On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited

Moni Naor and Omer Reingold

Abstract

Luby and Rackoff showed a method for constructing a pseudo-random permutation from a pseudo-random function. The method is based on composing four (or three for weakened security) so called Feistel permutations each of which requires the evaluation of a pseudo-random function. We reduce somewhat the complexity of the construction and simplify its proof of security by showing that two Feistel permutations are sufficient together with initial and final pair-wise independent permutations. The revised construction and proof provide a framework in which similar constructions may be brought up and their security can be easily proved. We demonstrate this by presenting some additional adjustments of the construction that achieve the following: 1. Reduce the success probability of the adversary. 2. Provide a construction of pseudo-random permutations with large input size using pseudo-random functions with small input size. 3. Provide a construction of a pseudo-random permutation using a single pseudo-random function.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Contact author(s)
reingold @ wisdom weizmann ac il
History
1997-02-17: revised
1996-08-01: received
Short URL
https://ia.cr/1996/011
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:1996/011,
      author = {Moni Naor and Omer Reingold},
      title = {On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 1996/011},
      year = {1996},
      note = {\url{https://eprint.iacr.org/1996/011}},
      url = {https://eprint.iacr.org/1996/011}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.