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.

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

Advertisements