# The Security of Many-Round {L}uby-{R}ackoff Pseudo-Random Permutations

## Ueli Maurer and Krzysztof Pietrzak

```
```Luby and Rackoff showed how to construct a (super-)pseudo-random
permutation $\{0,1\}^{2n}\ra\{0,1\}^{2n}$ from some number $m$ of
pseudo-random functions $\{0,1\}^{n}\ra\{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)\ra (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}\ra\{0,1\}^{n}$, denoted $\Psi^m_{2n}$, is
indistinguishable from a uniform random permutation
$\{0,1\}^{2n}\ra\{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.