Fixed-size hash function

In [Damg90a], length-reduction is required for all Jt e N. Of course, k = 1 should be excluded anyway, but constructions are simpler if larger bounds are permitted. For instance, if a family of groups where the discrete logarithm is hard does not contain any group whose elements are shorter than 10 bits, a construction of fixed-size hash functions from it will not yield any function that hashes to less than 10 bits. One could use different, trivial constructions for small it s, but it does not seem worth while. 

Tuple Exponentiation as 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. 

Fixed-size hash functions have been defined as functions on strings If k is the security parameter of the family of hash functions, then... 

Now the domains of the desired fixed-size hash functions are considered. The inputs are of length k and must be represented as elements of for some /i, where q has to be generated from k = make small(k ), i.e., only /I remains to be adapted. The family of groups guarantees... 

Theorem 8.51 (Tuple exponentiation as fixed-size hash functions). If... 

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

Figure 8.9. Construction of a hash function from a fixed-size hash function.

Each node value is computed by one application of the fixed-size hash function to the concatenation of its three children. 

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

In a concrete case, everything amounts to a choice of values k, I, and fi, such that the fixed-size hash functions are of the form... 

If these fixed-size hash functions are used in the construction of normal hash functions, each application of hashg deals with approximately pk-I bits of the message. One must minimize the time needed per message bit. Let... 

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. 

All the pre-reffered applications presuppose that an authenticating module that includes a certain cryptographic fimction called "hash function" is nested in the implementation of the application. Hash function H(M) is a transformation that takes an input message M and returns a fixed-size string, which is called the hash value h (that is, h = H(M)). Hash functions with just this property have a variety of general computational uses, but when employed in cryptography, the hash functions are usually chosen to have some additional properties. The basic requirements for a cryptographic hash function are as follows. 

---