Constructions in the Discrete-Logarithm Case

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. 

Definition 8.39. Let H be an Abelian group of order q and g. a /z-tuple of elements of H. (Later, q will usually be prime and g a tuple of generators.) A -relation is a multiplicative dependency between the components of g, i.e., a tuple y that fulfils the following predicate  

If q is prime and the isomorphism between N and is used, a -relation corresponds to a linear dependency between the exponents (cf. Lemma 8.2b). This is good to have in mind in the mathematical parts, but it cannot be exploited computationally. 

The following lemma collects a few simple dependencies between -relations, collisions, and discrete logarithms that should not get lost in the long computational parts. (Some of them are not needed in the following.) 

Lemma 8.40 (Mathematical parts). Let /f be an Abelian group of order q and g a -mple of elements of 7/. 

---

Table 8.2. Overview of the constructions in the discrete-logarithm case...

---