Publications: Abstract

# 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.