Strong claw-intractable family of permutation pairs

Deflnition 8.26. A strong claw-intractable family of permutation pairs... 

Theorem 8.57 (Iterated permutations as bundling functions). If a strong claw-intractable family of permutation pairs is given. Construction 8.56 defines a collision-intractable family of bundling functions. If the underlying family is weak, all properties except for the bundling property are still guaranteed. ... 

The construction of collision-intractable families of hiding homomorphisms from iterated squaring and doubling is basically Construction 8.58, based on the strong claw-intractable family of permutation pairs from Construction 8.64. Similar to the case with bundling homomorphisms, the functions B are replaced by B ... 

A complete formal description and a proof of a special case of bottom-up tree authentication (an optimized construction from strong claw-intractable families of permutation pairs) can be found in [Pfit89, PfWa90]. Hence only a sketch is presented here, whereas top-down tree authentication is treated in more detail. 

This section contains the constructions of some types of function families defined in Section 8.5.2 from a claw-intractable family of permutation pairs. An overview is given by the left half of the constractions in Figure 8.7. For some constructions, the underlying family may be weak, for others, it must be strong. 

Lemma 8.55. (Finding claws in collisions). Whenever a claw-intractable family of permutation pairs is given (strong or weak, see Definitions 8.26 and 8.27), the corresponding algorithm claw from collision is defined as follows. (Remember that with the conventions from Definition 8.5, the iterated functions are called Bf. ) It works on inputs of the form K, x, x ) with K e All, where X = (b, y) and x = (b , y ) with b, b e 0, 1 " and y, y e Df. ... 

The constructions in Section 8.2.3 had different properties depending on whether n was a generalized Blum integer or any element of 4N -1- 1. Thus two different families of good keys. Good and Good weak are provided they lead to a strong and a weak claw-intractable family of permutation pairs, respectively. 

One might say cryptologically strong instead, if one adheres to the convention from Footnote 3. However, this term is established, and the convention is not always respected anyway. Actually, they are simply called claw-free permutation pairs in [G0MR88]. The two name changes make the notation consistent with related collision-intractable or collision-free families of hash functions (see Section 8.5). The reasons are that the objects called claws do exist, it is only infeasible to find them, and that similar families without trap-doors are needed later. 

---