Information Security and Cryptography Research Group

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\}^{2n}\to\{0,1\}^{2n}$ 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 $\Psi^m_{2n}$, is indistinguishable from a uniform random permutation $\{0,1\}^{2n}\to\{0,1\}^{2n}$ by any computationally unbounded adaptive distinguisher making at most $2^{c n}$ queries for any $c<\alpha$, where $\alpha$ is a security measure and where queries are allowed from both the input and the output side.

Luby and Rackoff \cite{lubrac88} proved $\alpha=1/2$ for $m=4$. A natural problem, proposed by Pieprzyk \cite{pieprz90}, is to improve on $\alpha$ for larger $m$. The best known result, $\alpha=3/4$ for $m=6$, is due to Patarin \cite{patari98}. In this paper we prove $\alpha=1-O(1/m)$, i.e. that the (trivial) upper bound $\alpha=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},
}

Files and Links