On the construction of pseudorandom permutations : Luby-Rackoff revisited

Luby and Rackoff [26] showed a method for constructing a pseudorandom permutation from a pseudorandom 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 pseudorandom function. We reduce somewhat...

Full description

Saved in:
Bibliographic Details
Published in:Journal of cryptology 1999, Vol.12 (1), p.29-66
Main Authors: NAOR, M, REINGOLD, O
Format: Article
Language:English
Subjects:
Applied sciences
Cryptography
Exact sciences and technology
Information, signal and communications theory
Permutations
Pseudorandom
Security
Signal and communications theory
Telecommunications and information theory
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Luby and Rackoff [26] showed a method for constructing a pseudorandom permutation from a pseudorandom 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 pseudorandom 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 pairwise 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:• Reduce the success probability of the adversary. • Provide a construction of pseudorandom permutations with large input-length using pseudorandom functions with small input-length.
ISSN:0933-2790
1432-1378
DOI:10.1007/pl00003817