How collisions can be used to find claws

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. 

a) The major part of the computation is the applications of Bg. Polynomialtime algorithms for the individual permutations (or functions) are given, and the number of times they are applied is bounded by the length of the strings. 

---