The Security of Many-Round Luby-Rackoff Pseudo-Random Permutations
Ueli Maurer and Krzysztof Pietrzak
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},
}