Collision fixed-size hash functions

Now tuple exponentiation is turned into collision-intractable families of fixed-size hash functions. This was first done in [ChHP92] the construction was extended for the use in incremental signature schemes in [BeGG94]. In particular, one can use pair exponentiation, but larger tuples tiun out to be more efficient. 

Construction 8.52. (Part of the proof of Theorem 3.1 in [Damg90a].) Let a collision-intractable family of fixed-size hash functions be given with len(k) < - 1 for all fc > kig . The corresponding family of hash functions is defined by the following components, which are written with an asterisk to distinguish them from the components of the underlying family of fixed-size hash functions ... 

Remark 8.54. This family of hash functions can be augmented by short collision proofs according to Remark 8.37 The reduction used in the proof of the theorem yields a (rather obvious) algorithm to construct a collision of the underlying family of fixed-size hash functions, from any collision of the new family (for all acceptable keys, although it is only needed for correctly generated keys in the proof of collision-intractability). ... 

The following table summarizes the most important parameters of the constructions of collision-intractable families of bundling homomorphisms, hiding homomor-phisms, and fixed-size hash functions based on the discrete-logarithm assumption. Note that the main use of fixed-size hash functions is in the constmction of real hash functions. 

---