*Scribed by Siu-Man Chan *

** Summary **

Given one way permutations (of which discrete logarithm is a candidate), we know how to construct pseudorandom functions. Today, we are going to construct pseudorandom permutations (block ciphers) from pseudorandom functions.

**1. Pseudorandom Permutations **

Recall that a pseudorandom function is an efficient function , such that every efficient algorithm cannot distinguish well from , for a randomly chosen key and a random function . That is, we want that behaves like .

A pseudorandom permutation is an efficient function , such that for every key , the function mapping is a bijection. Moreover, we assume that given , the mapping is efficiently invertible (i.e. is efficient). The security of states that every efficient algorithm cannot distinguish well from , for a randomly chosen key and a random *permutation* . That is, we want that behaves like .

We note that the algorithm is given access to both an oracle and its (supposed) inverse.

**2. Feistel Permutations **

Given *any* function , we can construct a permutation using a technique named after Horst Feistel. The definition of is given by

where and are -bit strings. Note that this is an injective (and hence bijective) function, because its inverse is given by

Also, note that and are efficiently computable given .

However, needs not be a pseudorandom permutation even if is a pseudorandom function, because the output of must contain , which is extremely unlikely for a truly random permutation.

To avoid the above pitfall, we may want to repeat the construction twice. We pick two independent random keys and , and compose the permutations .

Indeed, the output does not always contain part of the input. However, this construction is still insecure, no matter whether is pseudorandom or not, as the following example shows.

Here, denotes the all-zero string of length , denotes the all-one string of length , and is . This shows that, restricting to the first half, is the complement of , regardless of .

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.

**3. The Luby-Rackoff Construction **

Let be a pseudorandom function, we define the following function : given a key and an input ,

It is easy to construct the inverse permutation by composing their inverses backwards.

Theorem 1 (Pseudorandom Permutations from Pseudorandom Functions)If is a -secure pseudorandom function computable in time , then is a secure pseudorandom permutation.

**4. Analysis of the Luby-Rackoff Construction **

Given four random functions , , let be the analog of Construction (3) 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 now prove Lemma 2 using a hybrid argument.

*Proof:* Consider the following five algorithms from to :

- : pick random keys , , , ,

- : pick random keys , , and a random function ,

- : pick random keys , and random functions ,

- : pick a random key and random functions ,

- : pick random functions ,

Clearly, referring to (5), gives the first probability of using all pseudorandom functions in the construction, and gives the second probability of using all completely random functions. By triangle inequality, we know that

We now construct an algorithm of complexity that distinguishes whether the oracle is or a random function .

- The algorithm picks keys and initialize data structures to to store pairs.
- The algorithm simulates . Whenever queries (or ), the simulating algorithm uses the four compositions of Feistel permutations, where
- On the first layers, run the pseudorandom function using the keys ;
- On the -th layer, run an oracle ;
- On the remaining layers, simulate a random function: when a new value for is needed, use fresh randomness to generate the random function at and store the key-value pair into the appropriate data structure; otherwise, simply return the value stored in the data structure.

When is , the algorithm behaves like ; when is a random function , the algorithm behaves like . Rewriting (6),

and is not -secure.

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

It is clear that Lemma 3 follows Lemma 4 and Lemma 5.

We now prove Lemma 4.

We shall prove Lemma 5 next time.