The Security of Many-Round Luby-Rackoff Pseudo-Random Permutations

Ueli Maurer and Krzysztof Pietrzak

Advances in Cryptology — EUROCRYPT 2003, Lecture Notes in Computer Science, Springer-Verlag, pp. 544–561, May 2003.

Luby and Rackoff showed how to construct a (super-)pseudo-random permutation ${0, 1}^{2 n} \to {0, 1}^{2 n}$ from some number $m$ of pseudo-random functions ${0, 1}^{n} \to {0, 1}^{n}$ . Their construction, motivated by DES, consists of a cascade of $m$ Feistel permutations. A Feistel permutation for a pseudo-random function $f$ is defined as $(L, R) \to (R, L \oplus f (R))$ , where $L$ and $R$ are the left and right part of the input and $\oplus$ denotes bitwise XOR or, in this paper, any other group operation on ${0, 1}^{*}$ . The only non-trivial step of the security proof consists of proving that the cascade of $m$ Feistel permutations with independent uniform random functions ${0, 1}^{n} \to {0, 1}^{n}$ , denoted $Ψ_{2 n}^{m}$ , is indistinguishable from a uniform random permutation ${0, 1}^{2 n} \to {0, 1}^{2 n}$ by any computationally unbounded adaptive distinguisher making at most $2^{c n}$ queries for any $c < α$ , where $α$ is a security measure and where queries are allowed from both the input and the output side.

Luby and Rackoff \cite{lubrac88} proved $α = 1 / 2$ for $m = 4$ . A natural problem, proposed by Pieprzyk \cite{pieprz90}, is to improve on $α$ for larger $m$ . The best known result, $α = 3 / 4$ for $m = 6$ , is due to Patarin \cite{patari98}. In this paper we prove $α = 1 - O (1 / m)$ , i.e. that the (trivial) upper bound $α = 1$ can be approached. The proof uses some new techniques that can be of independent interest.

BibTeX Citation

@inproceedings{MauPie03,
    author       = {Ueli Maurer and Krzysztof Pietrzak},
    title        = {The Security of Many-Round {L}uby-{R}ackoff Pseudo-Random Permutations},
    editor       = {Eli Biham},
    booktitle    = {Advances in Cryptology --- EUROCRYPT 2003},
    pages        = {544--561},
    series       = {Lecture Notes in Computer Science},
    year         = {2003},
    month        = {5},
    publisher    = {Springer-Verlag},
}