Construction de Luby-Rackoff
# Construction de Luby-Rackoff

En cryptologie, la construction de Luby-Rackoff est une technique permettant de construire des permutations dont on peut prouver qu'elles se comportent pratiquement comme des permutations pseudo-aléatoires, si on suppose l'existence de fonctions pseudo-aléatoires. De telles permutations jouent un rôle important dans la conception de cryptosystèmes, notamment des algorithmes de chiffrement par bloc, en ce qu'elles facilitent grandement l'analyse de leur sécurité. Il est toutefois important de noter que la construction de Luby-Rackoff est un modèle $idéalisé^,.$

La construction s'appuie sur les théorèmes de Luby-Rackoff, énoncés en 1988 par Michael Luby et Charles Rackoff, et dont l'importance dépasse cette seule $utilisation^,.$

Théorème de Luby-Rackoff — Un réseau de Feistel, instancié avec une fonction pseudo-aléatoire, réalise une permutation calculatoirement indistinguable d'une permutation pseudo-aléatoire dès que la profondeur du réseau dépasse 3.

Théorème fort de Luby-Rackoff — Le théorème précédent reste vrai face à un adversaire doté d'un oracle d'inversion, pour un réseau de Feistel de longueur au moins 4.

Les longueurs, de 3 et 4 respectivement, sont $optimales^,.$ D'un point de vue théorique, ce résultat montre que les fonctions pseudo-aléatoires (VRF) suffisent pour construire des permutations pseudo-aléatoires. Comme par ailleurs l'existence de générateurs pseudo-aléatoires (PRNG) permet classiquement de construire des VRF, on obtient une chaîne de réductions : $\mathrm {PRNG} \leq \mathrm {VRF} \leq \mathrm {PRP}$.

Depuis leur première preuve en 1988, les théorèmes de Luby-Rackoff ont été simplifiés et étendus de plusieurs $manières^,^,^,^,^,.$ Toutefois, les progrès dans la cryptanalyse des chiffrements à base de réseau de Feistel, des questions de performance, de nouveaux modèles d'attaque, et la découverte de nouvelles constructions pour le chiffrement par bloc (comme la construction de Lai-Massey) ont contribué à réduire la popularité des réseaux de Feistel utilisés dans la construction de Luby-Rackoff.

