A Construction from Pairs of Permutations

Assume that a pair (fo,/i) of permutations on a common domain D is given. From this pair, functions B and B (for cr 6 N) with bundling properties will be constructed. ( B stands for bundling.) The construction is due to [G0MR88], but it was only used for collision-intractability there, i.e., no bundling property was shown. 

The idea of the construction is as follows /q and/j are two functions such that each element z of D has one preimage under each of them, i.e., two preimages altogether. One can reinterpret them as one function where each z has two preimages by declaring the index 0 or 1 an additional parameter. To obtain many preimages for each z, instead of only 2, the application of this function is iterated. The resulting function is called B, and its restriction to exactly a iterations B j. 

Lemma 8.6. If/o and fi are permutations on their domain D, the iterated functions B and B jhave the following properties  

a) The function B(b, ) is a composition of permutations and thus a permutation, too. 

More formally, one would have to define B as an operator mapping function pairs to new functions, but the additional notation would not be justified in the following. 

---