CONSTRUCTION OF PSEUDORANDOM PERMUTATIONS

The permutation from {0, 1}2n to {0, 1}2n represented by S(f) in DES ( Data Encryption Standard) is used as the basic operation. Let f be a f unction from {0, 1}n to {0, 1}n and + denote bitwise exclusive or. The n S(f) is defined S(f)(L.R) = R.[L+f(R)] where L, R is-an-element-of { 0, 1}n. Moreover, let S(f2, f1, f0) denote the composition of S(f2), S (f1) and S(f0), and {S(f2, f1, f0)} denote a set of S(f2, f1, f0) obta ined when f0, f1 and f2 are chosen randomly from a set of pseudorandom functions. Luby et al. have shown that {S(f2, f1, f0)} is pseudorando m. This paper investigates the case in which there are two different p seudorandom functions and shows that while {S(f1, f1, f0)} and {S(f1, f0, f0)} are pseudorandom, {S(f0, f1, f0)} is not.