*Scribed by Anupam Prakash *

** Summary **

Today we finish the analysis of a construction of a pseudorandom permutation (block cipher) given a pseudorandom function.

**1. The Luby-Rackoff Construction **

Recall that if is a function, then we define the *Feistel permutation* associated with as

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

If are four functions, then is the same as the above construction but using the functions :

If is an oracle algorithm, we define as the probabilistic process in which we run a simulation of in which we reply to each query with a random answer.

**2. Today’s Proof **

The proof of the following result is what was missing from yesterday’s analysis.

Lemma 1For every non-repeating algorithm of complexity we have

*Proof:* The transcript of ‘s computation consists of all the oracle queries made by . The notation represents a query to the oracle at point while is a query made to the oracle at . The set consists of all valid transcripts for computations where the output of is 1 while consists of transcripts in consistent with being a permutation.

We write the difference in the probability of outputting 1 when given oracles and when given a random oracle as in as a sum over transcripts in .

We split the sum over into a sum over and and bound both the terms individually. We first handle the simpler case of the sum over .

The first equality holds as a transcript obtained by running using the oracle is always consistent with a permutation. The transcript generated by querying an oracle is inconsistent with a permutation iff. points with are queried. makes at most queries to an oracle that answers every query with an independently chosen random string from . The probability of having a repetition is at most .

Bounding the sum over transcripts in will require looking into the workings of the construction. Fix a transcript given by , with the number of queries . Each can be written as for strings of length corresponding to the left and right parts of . The string goes through iterations of using the function for the th iteration. The output of the construction after iteration , for input is denoted by .

Functions are said to be good for the transcript if the multisets and do not contain any repetitions. We bound the probability of being bad for by analyzing what happens when for some :

The algorithm does not repeat queries so we have . We observe that as equality together with equation (6) above would yield . This shows that equation (6) holds only if , for a fixed and distinct strings and . This happens with probability as the function takes values from independently and uniformly at random. Applying the union bound for all pairs ,

We use a similar argument to bound the probability of being bad. If for some we would have:

The algorithm does not repeat queries so we have . We observe that as equality together with equation (8) above would yield . This shows that equation (8) holds only if , for a fixed string and distinct strings and . This happens with probability as the function takes values from independently and uniformly at random. Applying the union bound for all pairs ,

Equations (7) and (9) together imply that

Continuing the analysis, we fix good functions , and the transcript . We will show that the probability of obtaining as a transcript in this case is the same as the probability of obtaining for a run of . Let . We calculate the probability of obtaining on query over the choice of and .

The values of the input are in bijection with pairs while the values of the output are in bijection with pairs , after fixing and . We have the relations (from (1)(3)):

These relations imply that can be an input output pair if and only if we have . Since and are random functions with range , the pair occurs with probability . The values and are distinct because the functions and are good. This makes the occurrence of independent from the occurrence of for . We conclude that the probability of obtaining the transcript equals .

The probability of obtaining transcript equals in the simulation as every query is answered by an independent random number from . Hence,

The statement of the lemma follows by adding equations (5) and (11) and using the triangle inequality.

This concludes the analysis of the Luby-Rackoff scheme for constructing pseudorandom permutations from a family of pseudorandom functions.