Impossibility and Optimality Results on Constructing Pseudorandom Permutations

Let I_n = {0, 1}n, and H_n be the set of all functions from I_n to I_n. For f ∈ H_n, define the DES-like transformation associated with f by F_{2n, f} (L, R) = (R ⊕ f(L), L), where L, R ε I_n. For f ₁, f₂, ..., f_s ∈ H_n, define Ψ(f_s, ..., f₂, f₁) = F_2n,fs, ∘ ... ∘ F_2n,f2 ∘ F_2n,f1. Our main result is that Ψ(fk, fj, fi) is not pseudorandom for any positive integers i, j, k, where fi denotes the i-fold composition of f. Thus, as immediate consequences, we have that (1) none of Ψ(f, f, f), Ψ(f, f, f2) and Ψ(f2, f, f) are pseudorandom and, (2) Ohnishi’s constructions Ψ(g, g, f) and Ψ(g, f, f) are optimal. Generalizations of the main result are also considered.