** Summary **

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 thatwhere 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 1If 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 2If 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 3For 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 4Let be a non-repeating algorithm of complexity at most . Then

where is a random permutation.

Finally, it remains to prove:

Lemma 5For every non-repating algorithm of complexity we have

We shall prove Lemma 5 next time.