Today we give a construction of a pseudorandom permutation (block cipher) given a pseudorandom function, and we begin its analysis.
1. Feistel Permutations
Let be a function. We define the Feistel permutation associated with as
Note that this is an injective (and hence bijective) function, because its inverse is given by
Also, note that and are efficiently computable given .
Unfortunately, it is clear that, even if is a pseudorandom function, then does not look like a random permutation: is zero in half of its bits. (By we mean a sequence of zeroes.)
Also, even repeating the construction twice does not help. If we pick two random keys , and consider the permutation , then does not look like a random permutation: consider and , and notice that the first bits of the first string are the complement of the first bits of the second string.
What happens if we repeat the construction three times? We still do not get a pseudorandom permutation.
Exercise 1 (Not Easy) Show that there is an efficient oracle algorithm such that
where is a random permutation, but for every three functions , if we define we have
Finally, however, if we repeat the construction four times, with four independent pseudorandom functions, we get a pseudorandom permutation.
2. The Luby-Rackoff Construction
Let be a pseudorandom function, we define the following function : given a key and an input ,
Theorem 1 If is a -secure pseudorandom function computable in time , then is a secure pseudorandom permutation.
3. Analysis of the Luby-Rackoff Construction
Given four random functions , , let be the analog of Construction (2) using the random function instead of the pseudorandom functions ,
We prove Theorem 1 by showing that
- is indistinguishable from or else we can break the pseudorandom function
- is indistinguishable from a random permutation
The first part is given by the following lemma, which we prove via a standard hybrid argument.
Lemma 2 If is a -secure pseudorandom function computable in time , then for every algorithm of complexity we have
And the second part is given by the following lemma:
Lemma 3 For every algorithm of complexity we have
where is a random permutation.
We say that an algorithm is non-repeating if it never makes an oracle query to which it knows the answer. (That is, if is interacting with oracles for some permutation , then will not ask twice for for the same , and it will not ask twice for for the same ; also, after getting the value in an earlier query, it will not ask for later, and after getting it will not ask for later. )
We shall prove Lemma 3 for non-repeating algorithms. The proof can be extended to arbitrary algorithms with some small changes. Alternatively, we can argue that an arbitrary algorithm can be simulated by a non-repeating algorithm of almost the same complexity in such a way that the algorithm and the simulation have the same output given any oracle permutation.
In order to prove Lemma 3 we introduce one more probabilistic experiment: we consider the probabilistic algorithm that simulates and simulates every oracle query by providing a random answer. (Note that the simulated answers in the computation of may be incompatible with any permutation.)
We first prove the simple fact that is close to simulating what really happen when interacts with a truly random permutation.
Lemma 4 Let be a non-repeating algorithm of complexity at most . Then
where is a random permutation.
Finally, it remains to prove:
Lemma 5 For every non-repating algorithm of complexity we have
We shall prove Lemma 5 next time.