Discrete logarithm

Shor, P. W. Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer. Proc. 35th Annual Symposium on the Foundations of Computer Science Goldwasser, S. Ed. IEEE Computer Society Press Los Alamos, CA, 1994, p. 124. 

This formula is applied successively to obtain the integral over a large interval. To obtain the results which follow, p(l ) was evaluated at 20 discrete, logarithmically spaced values of l between 10 2and 10s Debye lengths. This was found to keep the relative error in 0dl(.v), due to numerical integration, below 0.1%. 

The practical complexity of the discrete logarithm has developed surprisingly similar to that of factoring (see Section 8.4.2), although no reduction between the two problems is known. As a consequence, the efficiency of the ElGamal scheme and RSA is rather similar, too. 

This implies that all types of schemes also exist both on the factoring assumption and on a discrete-logarithm assumption (with [Damg88]). 

The bank is the stronger partner in several ways. It can select the signature schemes and security parameters and thus provide for its own security. Moreover, it can inform itself about how trustworthy the cryptologic assumption is, both initially and while the scheme is in use, whereas many clients will already be deterred by the name of a factoring or discrete-logarithm assumption. 

All these simplifications can be applied to the construction of efficient fail-stop signature schemes based on the discrete-logarithm assumption, see Remark 9.16. 

Any cyclic group G is isomorphic to the additive group of integers modulo IGI. For any generator g, the exponentiation function expgix) = g is an isomorphism into G. The inverse is the discrete-logarithm function logg. In particular, G is Abelian, i.e., commutative. 

Section 8.2.1 treats the discrete-logarithm case and Section 8.2.3 the factoring case. Both sections are slightly more comprehensive than needed in this text, because these function classes may have more applications in future. In between. Section 8.2.2 contains an abstract construction from pairs of permutations on a... 

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

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

Part a) of this lemma corresponds to Lemma 8.3 for the discrete-logarithm case and has the same consequence The result z gives no (Shannon) information about the first parameter, b, if the second parameter, y, is chosen uniformly at random from D. This is a hiding property again. 

Part b) of this lemma corresponds to Lemma 8.3 for the discrete-logarithm case, and it has the same two consequences ... 

The second assumption used in the following is that groups H of prime order q exist where computing discrete logarithms is infeasible, i.e., an assumption slightly different from that mentioned in Section 2.4. (Some benefits of groups of prime order were already shown in Section 8.2.1.)... 

The following abstract assumption is unusual in the sense that it considers different interest groups. One party selects the group where computing discrete logarithms is assumed to be hard. The other party needs to be sure that what has been generated is... 

Other more or less formal abstract discrete-logarithm assumptions, such as in [BoKK90, McCu90, OkSS93] differ in the following points (apart from the absence of sets All0 Does one need... 

Moreover, if the groups are not cyclic, one can partition the discrete-logarithm problem into a decision problem whether a discrete logarithm exists and the computation. 

The most well-known and well-investigated discrete-logarithm assumption is that for multiplicative groups of finite prime fields, i.e., the cyclic groups "ZLp of order p - 1. It is called the standard discrete-logarithm assumption in the foUowing. Of coiu-se, p - 1 is even and therefore not a prime, hence these groups cannot be used directly here. 

Similar to the situation with factoring, one often excludes primes p where p - 1 has no large prime factors, because computing discrete logarithms is much easier in that case [PoHe78]. 

Lemma 8.23. If the discrete logarithm is hard for the given generation scheme for subgroups of prime fields, Construction 8.22 is a family of groups of prime order where the discrete logarithm is hard. ... 

Proof. All the algorithms are obviously polynomial-time in the correct parameters. What remains to be shown is Properties a) and P) from Definition 8.19a and that the discrete logarithm is hard according to Definition 8.19b. 

In practice, discrete logarithms have been computed for primes p of about 200 bits. However, not so much work has gone into computing discrete logarithms as into factoring. 

On quantum computers, computing discrete logarithms is possible in random polynomial time [Shor94]. 

If one wants a relation with the standard discrete-logarithm assumption, one must ensure that the quotient d = p-V)lq, i.e., the index of the subgroup, is only polynomial in k. 

In this case, any method to compute discrete logarithms in the subgroup H p leads to a method to compute discrete logarithms in 2 with overhead polynomid in k (following ideas from [PoHe78]) Given g,g e 7Z.p, first compute the... 

Anyway, primes p with one very large prime factor q are usually regarded as the hardest cases for discrete-logarithm algorithms. 

Three other concrete discrete-logarithm assumptions that could be used are mentioned. 

---