On the construction of pseudorandom permutations: Luby-Rackoff revisited (Q1284012)

The notion of pseudorandom permutations has been introduced by \textit{M. Luby} and \textit{C. Rackoff} [SIAM J. Comput. 17, 373-386 (1988; Zbl 0644.94018)] to formalize the well-known notion of block ciphers. Luby and Rackoff also showed a method for constructing a pseudorandom permutation from a pseudorandom function. Their construction consists of four (or three for weaker notion of security) rounds of so-called Feistel permutations, where each round involves an application of a pseudorandom function. In the paper the construction is simplified and its complexity improved. First, a brief introduction and review of results and related work is given followed by a section devoted to notation and definitions used in the paper. Then, the principal idea of the new approach is explained. Particularly, it is argued that the different rounds of the original Luby-Rackoff construction serve significantly different roles. This observation is then used to present the main construction where pairwise independent permutations replace the first and fourth rounds of the Luby-Rackoff construction. Proof of the security of the new construction is given as well. Then, the high-level structure of the proof is reviewed to provide a framework that enables one to relax and generalize the main construction. In next three sections variations of the main construction are studied. For example it is shown that it is possible to convert the construction into another one that makes use of only single pseudorandom function (instead of two) or that one can use even weaker permutations instead of the pairwise independent ones. Also a simple generalization using \(t\) rounds of Feistel permutations instead of two is described and analyzed as well as another generalization that uses pseudorandom functions on a single block to construct strong pseudorandom permutations on many blocks. Finally different constructions given in the paper are analyzed as constructions of \(k\)-wise \(\delta\)-dependent permutations and the paper ends with a brief discussion of directions for further research.