Constructions from Claw-Intractable Pairs of Permutations

The basic idea is from [G0MR88] it was first applied to hash functions in [Damg88] and to bundling and hiding functions in [Pfit89, PfWa90]. 

On the left, one sees how a claw is found where the two paths ending at z meet on the right, one sees the exception where one of the two bit strings is a prefix of the other. 

The common part of the two paths corresponds to the conomon prefix of the two bit strings that are the first parameters of the iterated function B. (Recall that these bit strings are evaluated back to front.) Hence a collision leads to a claw if and only if neither of the two strings is a prefix of the other. For instance, this is clear if only bit strings of a fixed length 7 are considered at the same time, as in the functions 

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.  

More formally, one would have to define claw from collision as an operator mapping a family of permutation pairs to an algorithm, but, similar to the notations B etc. from Definition 8.5, the additional notation would not be justified. 

---