Tuple exponentiation

The basic functions with a bundling property in the discrete-logarithm case are simply products of several exponentiations. This is called tuple exponentiation or, if the number of components is known to be jti,/x-tuple exponentiation. Pair exponentiation seems to have been first used like this in [B0CT88], larger tuples in [ChHP92]. 

Some simple mathematical properties of tuple exponentiation follow. 

The most important case is that where the group order, q, is prime. Then is a field, and as its multiplicative group is cyclic, a tuple-exponentiation equation corresponds to a linear equation in the exponents (by Lemma 8.2b). Hence one can determine the number of solutions to such equations. ... 

Of course, computing the linear equation corresponding to a given tuple exponentiation equation is related to computing discrete logarithms, and computationally restricted participants will not be able to exploit it (see Seetion 8.5.3). 

The number of multiplications can be reduced. Techniques for the case where the basis is a variable can be found in [KnutSl, BoCo90, SaDi93] however, none of them achieves less than Z squarings and multiplications altogether. (For more details, see the next subsection, /t-Tuple Exponentiation .) If the basis g is fixed and only the exponent varies, precomputation of some powers of g can help to a reduction to about Z /log2(Z ) multiplications [BGMW93]. ... 

The product of several exponentiations, i.e., a t-tuple exponentiation g- as in Definition 8.1, can be computed more efficiently than by computing all the products separately and multiplying them. In the following, small tuples are often used, e.g., with /i = 3. In such cases, the simplest technique (attributed to Shamir in [ElGa85]) is an extension of the square-and-multiply algorithm that evaluates exponents from left to right After each squaring, the intermediate result is multiplied with a product where h,- is the appropriate bit of x,-. A table with the 2 ... 

In abstract constructions, the domains Gg are written additively and the codomains Hg multiplicatively. This notation corresponds to the discrete-logarithm case, where hg is tuple exponentiation. Note that homomorphisms automatically have a bundling property if the domain is sufficiently larger than the codomain, as in Lemma 8.17. 

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. 

The first generalization is to assume that the size of the tuples, is arbitrary, but fixed before the security parameter k. This was done in [ChHP92]. Tuple exponentiation for jU > 2 was also considered in [ChEG88] already, but the theorem stated there (without proof) neither easily implies nor is easily implied by the theorems needed in the other articles. 

This will be led to a contradiction with Theorem 8.41, the collision-intractability of tuple exponentiation, for the case Qmu = 2 An algorithm A is constructed such toat, for the same constant c Vfeg 3 o-... 

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. 

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

---