Collision hash functions

Because hashing is a one-way function and the output of the function has a low probability of collisions, hashing can be used with the cryptographic product or services family for authentication, nonrepudiation, and data integrity. An example of these is the Digital Notary.3 Hashing is also a key element in the DSA. 

One might say cryptologically strong instead, if one adheres to the convention from Footnote 3. However, this term is established, and the convention is not always respected anyway. Actually, they are simply called claw-free permutation pairs in [G0MR88]. The two name changes make the notation consistent with related collision-intractable or collision-free families of hash functions (see Section 8.5). The reasons are that the objects called claws do exist, it is only infeasible to find them, and that similar families without trap-doors are needed later. 

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. 

One basic idea for these constructions is tree authentication. If one starts with the type sketched in Section 2.4, the same addition is needed as with message hashing The hash functions used must be collision-intractable, and their collisions count as proofs of forgery. 

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

The property that makes all the functions with bundling properties, and also some other functions such as hash functions, interesting for cryptology is that it is infeasible to find collisions, i.e., two values with the same image see Figure 8.4 (and Figure 6.9). For precision, this notion and two related ones are given formal definitions. 

This implies that collision-intractable hash functions as used in practice (e.g., [SHS92]) are formally undefinable. 

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

Note that a weaker notion of families of hash functions exists, too, so-called families of universal one-way hash functions [NaYu89]. However, in the applications to fail-stop signature schemes, collision-intractability is needed. 

Definition 8.35. A collision-intractable family of hash functions has the... 

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

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. 

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

A collision of the hash function cormts as a valid proof of forgery. 

The key for the family of hash functions, i.e., the description of the particular function used, must be chosen by the risk bearer s entity (because collision-intractability is only guaranteed against parties who did not generate this key). Hence in schemes with prekey, this key is a part of the prekey. 

Remark 10.6 (Two variants of broken ). If a collision of the hash function occurs as a proof of forgery, it is sufficient to choose a new hash function, whereas one can retain the prekey prek from the underlying scheme and the values sk and mk. As the keys of the hash functions were assumed to be locally verifiable, only the risk bearer(s) have to publish a new key of a hash function after such a proof of forgery, whereas the signers need not send any new information. This may be helpful if one decides to use fast, but not provably collision-intractable hash functions. 

With fast, but not provably collision-intractable hash functions, small s, e.g., of length 160, can be used in the signature scheme. 

Verifying proofs of forgery It is verified that the proof is either a collision of the hash function or a valid proof of forgery in the one-time scheme. 

Damg88 Ivan Bjerre Damgwd Collision free hash functions and public key signature schemes Eurocrypt 87, LNCS 304, Springer-Verlag, Berlin 1988, 203-216. 

MiOI91 Shoji Miyaguchi, Kazuo Ohta, Masahiko Iwata Confirmation that Some Hash Functions are not Collision Free Eurocrypt 90, LNCS 473, Springer-Verlag, Berlin 1991, 326-343. 

A hashing function is only as good as the number of collisions it avoids. As the number of possible collisions increases, the weaker the hashing function becomes. While it is often impossible to avoid collisions, we want to prevent them as much as possible. 

Although this hashing function works well, it cannot avoid collisions. Currently, both Joseph Marshall Pollan, bom on October 19, 1970, and John Michael Pollan, bom on October 19, 1970, are in the system. Suppose a new driver, Jessica Mosher Pollard, also bom on October 19, 1970, were to be entered into the system. A collision could not be avoided unless the hashing function used to create these driver s license numbers were altered. 

Identify two different situations where a collision could occur when using this hashing function. Explain each type of collision and give an example of each one. 

Now, suppose that Jessica Mosher Pollard, bom on October 19, 1970, needs to be assigned a number. The alternative month code has already been used, so a collision will occur unless the hashing function is somehow altered. Without such an alteration, her driver s license number will be either POLLAJM304PR or POLLAJM3047R. Either way, two people will be assigned the same number and a collision will occur. It is because the function is not one-to-one that problems result. When Jessica s number is typed into a computer, either Joseph s or John s records may be retrieved. Consequently, having no collisions (a one-to-one function) is very desirable. This function should be onto, as well. Otherwise, extra numbers will be floating around in the system without any drivers associated with them. This could cause data entry and retrieval problems. 

Most full-structure search systems use a hashing scheme to quickly locate potential matches and then perform a full lexical comparison of the name. A hashing function is used that takes the canonical name as input and returns a disk location to store and retrieve the name from. The number of hash collisions (where two different structures have the same hash value) is dependent on the hash function used and percentage utilization of the hash space. This database access method means that search speeds are relatively independent of database size, except where excessive hash collisions occur or numerous matches occur. 

---