Today we finish the analysis of a construction of a pseudorandom permutation (block cipher) given a pseudorandom function.
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.
The proof of the following result is what was missing from yesterday’s analysis.