Collision-intractable family

Moreover, [DaPP94] contains a construction from an arbitrary so-called collision-intractable family of hash functions, which is fairly efficient at least if one trusts a fast, but not cryptographically strong hash function, and may therefore be a reasonable alternative if number-theoretic assumptions should be disproved. 

This property, which will guarantee availability of service in the chosen model, is only defined here, but not always required, because that would exclude the general abstract construction with message hashing, unless the notion of hash functions were modified significantly. However, the constructions with concrete collision-intractable families of hash functions can be modified to have this property (see Section 10.1). 

Several classes of collision-intractable functions can be defined. Important ones are collision-intractable families of... 

Definition 8.29. A collision-intractable family of bundling functions... 

Definition S.30. A coliision-intractabie family of bundling homomorphisms is a collision-intractable family of bundling functions with the following additional properties and components ... 

As with most other classes of function families, there is not only one definition of collision-intractable families of hash functions. 

After all the mathematical and computational preparations, it is quite clear that pair exponentiation in a family of groups of prime order where the discrete logarithm is hard yields a collision-intractable family of bundling homomorphisms. (It was first used in this way in [HePe93].) It only remains to be decided how the security parameters are related, because the family of groups has only one, k, whereas the family of bundling homomorphisms has two, say k and T for distinction. The following facts are known ... 

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

Theorem 8.53. (Adapted from [Damg90a, Theorem 3.1]). Construction 8.52 is a collision-intractable family of hash functions. ... 

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. 

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 a collision-intractable family of bundling homomorphisms from iterated squaring and doubling is basically Construction 8.56, based on the claw-intractable families of permutation pairs from Construction 8.64. The new points are ... 

Theorem 8.67 (Iterated squaring and doubling as bundling homomor-phisms). On the factoring assumption. Construction 8.66 defines a collision-intractable family of bundling homomorphisms. ... 

Proof. The construction is a collision-intractable family of hiding functions according to Theorem 8.59 and Lemma 8.65. (The replacement of B by B can be handled as in the proof of Theorem 8.67.) The functions Hr are homomorphisms between groups Gr and Hj according to Theorem 8.16, and is obviously an Abelian group, too. It remains to be shown that Kr is a homomorphism. This is not completely trivial, although TCg is simply a projection, because Gg as a group is not the direct product of Z2T and RQR , but one can immediately see it from the definition of the operation ... 

In this section, a framework for constructing standard fail-stop signature schemes with prekey for signing one message block from a collision-intractable family of bundling homomorphisms is described. Two parameters (the exact family of... 

A collision-intractable family BundFam of bundling homomorphisms. The same... 

BundFam, the collision-intractable family of bundling homomorphisms, is given by Construction 8.44, i.e., pair exponentiation in the given family of groups. Its... 

Collision-intractable families of hash functions have to be used. 

---