Weak claw-intractable family of permutation pairs

Definition 8.27. A weak claw-intractable family of permutation pairs... 

Construction 8.56. Let a weak claw-intractable family of permutation pairs be given (see Definition 8.27). The corresponding family of iterated permutations as bundling functions is defined by the following components, which are written with an asterisk to distinguish them from the components of the family of permutation pairs ... 

Theorem 8.62 (Iterated permutations as hash functions). If a weak claw-intractable family of permutation pairs is given. Construction 8.61 defines a collision-intractable family of hash functions. ... 

Hence this section starts with the construction of claw-intractable families of permutation pairs from these functions. In addition to the results that are then a consequence of Section 8.5.4, most function families in this section are families of homomorphisms, and one can use the results of Section 8.2.3 to show a bundling property even if only a weak claw-intractable family of permutation pairs is given. 

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. 

Before Construction 8.61 can be applied to the weak claw-intractable family of permutation pairs from Construction 8.64, a fixed-length encoding must be fixed. The sets to be encoded are RQR with I/1I2 2k. One can simply represent all their elements as binary numbers of length 2k with leading zeros. Furthermore, the standard prefix-free encoding, prefix Jree, is used for the messages. This yields the following construction. 

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. ... 

---