Scribed by Anupam Prakash
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.
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 .
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 ,
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 .
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 .
This concludes the analysis of the Luby-Rackoff scheme for constructing pseudorandom permutations from a family of pseudorandom functions.