New Results on Pseudorandom Permutation Generators Based on the Des Scheme

We denote by ψk the permutation generator based on the DES Scheme with k rounds where the S boxes are replaced by random independant functions. We denote by |P₁ − P₁*|, (respectively |P₁ − P₁**|), the probability of distinguishing such a permutation from a random function (respectively from a random permutation) by means of a distinguishing circuit that has m oracle gates.In 1988, M. Luby and C. Rackoff [1] proved that $$ \forall k \geqslant 3,|P_1 - P_1^* | \leqslant \frac{{m(m - 1)}} {{2^n }}. $$At Eurocrypt 90, J. Pieprzyk wondered at the end of his paper [4] if that inequality could be improved. This is the problem we consider here. In particular, such an improvement could greatly reduce the length of the keys used in a “direct” application of these theorems to a cryptosystem.Our main results will be: 1.For ψ3 and ψ4 there is no really tighter inequality than $$ \leqslant \frac{{m(m - 1)}} {{2^n }} $$ .2.However for ψ5 (and then for ψk, k ≥ 5), there is a much tighter inequality than Luby - Rackoff’s one. For example for ψ6, |P₁ − P₁*| and |P₁ − P₁**| are $$ \leqslant \frac{{12m.}} {{2^n }} + \frac{{18m^3 }} {{2^{2n} }} $$ .3.When m is very small (m = 2 or 3 for example) it is possible to have an explicit evaluation of the effects of the number of rounds k on the “better and better pseudorandomness” of ψk.