Big Chemical Encyclopedia

Chemical substances, components, reactions, process design ...

Articles Figures Tables About

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]. [Pg.219]

Some simple mathematical properties of tuple exponentiation follow. [Pg.220]

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. ... [Pg.220]

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). [Pg.220]

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]. ... [Pg.229]

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 ... [Pg.230]

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. [Pg.247]

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. [Pg.254]

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. [Pg.255]

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-... [Pg.264]

Tuple Exponentiation as Fixed-Size Hash Functions... [Pg.266]

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. [Pg.266]

Theorem 8.51 (Tuple exponentiation as fixed-size hash functions). If... [Pg.269]


See other pages where Tuple exponentiation is mentioned: [Pg.219]    [Pg.219]    [Pg.220]    [Pg.230]    [Pg.243]    [Pg.247]    [Pg.254]    [Pg.254]    [Pg.266]    [Pg.268]    [Pg.268]    [Pg.270]    [Pg.272]    [Pg.273]    [Pg.303]    [Pg.310]   
See also in sourсe #XX -- [ Pg.219 , Pg.230 ]




SEARCH



Tuple

© 2024 chempedia.info