ABSTRACT
This chapter shows how pseudorandom permutations and strong pseudorandom permutations can be constructed from any pseudorandom function. The reason is that constructions of such hash functions from one-way functions are unknown and, in fact, there is evidence suggesting that such constructions are impossible. A hybrid argument is a basic tool for proving indistinguishability when a primitive is applied multiple times. Somewhat informally, the technique works by defining a series of intermediate “hybrid distributions” that bridge between two “extreme distributions” that we wish to prove indistinguishable. The formal definition of computational indistinguishability refers to probability ensembles, which are infinite sequences of probability distributions. Many of the other definitions and assumptions in this book can also be cast as special cases or variants of computational indistinguishability.
