Collision-intractable

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. 

It must be computationally infeasible to find a collision, i.e., a pair of values with the same image (e.g., two secret keys corresponding to the same public key) see Figure 6.9. Such functions are called collision-intractable. ... 

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

Assume that a pair (fo,/i) of permutations on a common domain D is given. From this pair, functions B and B (for cr 6 N) with bundling properties will be constructed. ( B stands for bundling.) The construction is due to [G0MR88], but it was only used for collision-intractability there, i.e., no bundling property was shown. 

Collision-intractability is the computational property that it is infeasible to find collisions. It is only defined for families of functions For any single function that has a collision in the mathematical sense, there is an algorithm with constant running time that, independent of any input, always outputs this collision. ... 

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

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

Important classes with other properties related to collision-intractability are 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. 

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. 

Computational requirements Collision-intractable Collision-intractable with respect to equal r-images Collision-intractable... 

This subsection considers the collision-intractability of tuple exponentiation. It is shown that it is infeasible to find exp -collisions for tuples of generators of groups of prime order where the discrete logarithm is hard. First, a related simpler notion, that of multiplicative relations between given generators, is defined. 

Theorem 8.41 (Collision-intractability of poly(ll)-tnple exponentiation in groups of prime order). Let a family of groups of prime order be given where the discrete logarithm is hard. For every probabilistic polynomial-time algorithm A (that tries to compute collisions) and every polynomial Qmu (determining the growth of /i as a function of k) ... 

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

D. Collision-intractability (8.29d). Assume that there were a probabilistic polynomial-time algorithm A that computed collisions better than permitted in Definition 8.29d, i.e., there is a polynomial Qtau and a constant c> 0 such that /k 3k >k 3t [Pg.264]

---