Index-calculus algorithm

The index-calculus algorithm is the most powerful method known for computing discrete logarithms. The technique employed does not apply to all groups, but when it does, it often gives a subexponential-time algorithm. The algorithm is first described in the general setting of a cyclic group G (Algorithm 3.68). Two examples are then presented to illustrate how the index-calculus algorithm works in two kinds of groups that are used in practical applications, namely Z* (Example 3.69) and Fg,,, (Example 3.70).

The index-calculus algorithm requires the selection of a relatively small subset S of elements of G, called the factor base, in such a way that a significant fraction of elements of G can be efficiently expressed as products of elements from S. Algorithm 3.68 proceeds to precompute a database containing the logarithms of all the elements in S, and then reuses this database each time the logarithm of a particular group element is required.

The description of Algorithm 3.68 is incomplete for two reasons. Firstly, a technique for selecting the factor base 5 is not specified. Secondly, a method for efficiently generating relations of the form (3.5) and (3.7) is not specified. The factor base S must be a subset of G that is small (so that the system of equations to be solved in step 3 is not too large), but not too small (so that the expected number of trials to generate a relation (3.5) or (3.7) is not too large). Suitable factor bases and techniques for generating relations are known for some cyclic groups including Z* (see §3.6.5(i)) and FJjm (see §3.6.5(h)), and, moreover, the multiplicative group F* of a general finite field Fg.

3.68 Algorithm Index-calculus algorithm for discrete logarithms in cyclic groups

INPUT: a generator a of a cyclic group G of order n, and an element ,3 e G.

OUTPUT: the discrete logarithm у = logQ /3.

  • 1. (Select a factor base S) Choose a subset S = {pi, p2, • • • • pt} of G such that a “significant proportion” of all elements in G can be efficiently expressed as a product of elements from S.
  • 2. (Collect linear relations involving logarithms of elements in S)
  • 2.1 Select a random integer к, 0 < к < n - 1, and compute ak.
  • 2.2 Try to write ak as a product of elements in S:

If successful, take logarithms of both sides of equation (3.5) to obtain a linear relation

  • 2.3 Repeat steps 2.1 and 2.2 until t + c relations of the form (3.6) are obtained (c is a small positive integer, e.g. c = 10, such that the system of equations given by the t + c relations has a unique solution with high probability).
  • 3. (Find the logarithms of elements in S) Working modulo n, solve the linear system of t + c equations (in t unknowns) of the form (3.6) collected in step 2 to obtain the values of logQp,, 1 < i
  • 4. (Compute у)
  • 4.1 Select a random integer к, 0 < к < n - 1, and compute (3 ■ ak.
  • 4.2 Try to write 0 ■ ak as a product of elements in S:

If the attempt is unsuccessful then repeat step 4.1. Otherwise, taking logarithms of both sides of equation (3.7) yields loga 0 = logQ p,k) mod n;

thus, compute у = (Xw=i & logQ p, - k) mod n and retum(y).

(i) Index-calculus algorithm in Z*

For the field Zp, p a prune, the factor base S can be chosen as the first t prime numbers. A relation (3.5) is generated by computing ak mod p and then using trial division to check whether this integer is a product of primes in S. Example 3.69 illustrates Algorithm 3.68 in Z* on a problem with artificially small parameters.

  • 3.69 Example (Algorithm 3.68 for logarithms in Z^q) Let p = 229. The element a = 6 is a generator of Z229 of order n = 228. Consider 3 = 13. Then logG 13 is computed as follows, using the index-calculus technique.
  • 1. The factor base is chosen to be the first 5 primes: S = {2.3,5,7,11}.
  • 2. The following six relations involving elements of the factor base are obtained (unsuccessful attempts are not shown):

These relations yield the following six equations involving the logarithms of elements in the factor base:

  • 3. Solving the linear system of six equations in five unknowns (the logarithms ж, = logo Pi) yields the solutions logG 2 = 21, logG 3 = 208, log6 5 = 98, log6 7 = 107, and logG 11 = 162.
  • 4. Suppose that the integer к = 77 is selected. Since 3 ■ ak = 13 • 677 mod 229 = 147 = 3 • 72, it follows that

(ii) Index-calculus algorithm in F2m

The elements of the finite field F2™ are represented as polynomials in Z2 [ж] of degree at most m — 1, where multiplication is performed modulo a fixed irreducible polynomial /(ж) of degree m in Z2 [ж] (see §2.6). The factor base 5 can be chosen as the set of all irreducible polynomials in Z2 [ж] of degree at most some prescribed bound b. A relation (3.5) is generated by computing ak mod /(ж) and then using trial division to check whether this polynomial is a product of polynomials in 5. Example 3.70 illustrates Algorithm 3.68 in F2,„ on a problem with artificially small parameters.

  • 3.70 Example (Algorithm 3.68 for logarithms in F2?) The polynomial /(ж) = ж7 + ж + 1 is irreducible over Z2. Hence, the elements of the finite field F2t of order 128 can be represented as the set of all polynomials in Z2 [ж] of degree at most 6, where multiplication is performed modulo /(ж). The order of F2t is n = 27 - 1 = 127, and a = ж is a generator of F27. Suppose 0 = ж4 + ж3 + ж2 + ж + 1. Then у = logx 0 can be computed as follows, using the index-calculus technique.
  • 1. The factor base is chosen to be the set of all irreducible polynomials in Z2 [ж] of degree at most 3: S = {ж, ж + 1, ж2 + ж + 1, ж3 + ж + 1. ж3 + ж2 + 1}.
  • 2. The following five relations involving elements of the factor base are obtained (unsuccessful attempts are not shown):

These relations yield the following five equations involving the logarithms of elements in the factor base (for convenience of notation, let pi = logx ж, p2 = log^-l

  • 3. Solving the linear system of five equations in five unknowns yields the values pi = 1, P2 = 7,рз = 56, pi = 31, andps = 90.
  • 4. Suppose к = 66 is selected. Since

it follows that

  • 3.71 Note (running time of Algorithm 3.68) To optimize the running time of the index-calculus algorithm, the size t of the factor base should be judiciously chosen. The optimal selection relies on knowledge concerning the distribution of smooth integers in the interval [1, p — 1] for the case of Z*, and for the case of F^m on the distribution of smooth polynomials (that is, polynomials all of whose irreducible factors have relatively small degrees) among polynomials in F2[:r] of degree less than m. With an optimal choice of t, the index-calculus algorithm as described above for Z* and F^m has an expected miming time of Lq[, c] where q = p or q = 2m, and c > 0 is a constant.
  • 3.72 Note (fastest algorithms known for discrete logarithms in Z* and F^m) Currently, the best algorithm known for computing logarithms in F^,,, is a variation of the index-calculus algorithm called Coppersmith’s algorithm, with an expected miming tune of L2m [|, c] for some constant c < 1.587. The best algorithm known for computing logarithms in Z* is a variation of the index-calculus algorithm called the number field sieve, with an expected running time of Lp[|, 1.923]. The latest efforts in these directions are surveyed hi the Notes section (§3.12).
  • 3.73 Note (parallelization of the index-calculus algorithm)
  • (i) For the optimal choice of parameters, the most time-consuming phase of the index- calculus algorithm is usually the generation of relations involving factor base logarithms (step 2 of Algorithm 3.68). The work for this stage can be easily distributed among a network of processors by simply having the processors search for relations independently of each other. The relations generated are collected by a central processor. When enough relations have been generated, the corresponding system of linear equations can be solved (step 3 of Algorithm 3.68) on a single (possibly parallel) computer.
  • (ii) The database of factor base logarithms need only be computed once for a given finite field. Relative to this, the computation of individual logarithms (step 4 of Algorithm 3.68) is considerably faster.

Discrete logarithm problem in subgroups of Z*p

The discrete logarithm problem in subgroups of Z* has special interest because its presumed intractability is the basis for the security of the U.S. Government NIST Digital Signature Algorithm (§11.5.1), among other cryptographic techniques.

Let p be a prime and q a prime divisor of p - 1. Let G be the unique cyclic subgroup of Z* of order q, and let q be a generator of G. Then the discrete logarithm problem in G is the following: givenp, q, a, and /3 € G, find the unique integer x, 0 < x < q -1, such that ax = (3 (mod p). The powerful index-calculus algorithms do not appear to apply directly in G. That is, one needs to apply the index-calculus algorithm in the group Z* itself in order to compute logarithms in the smaller group G. Consequently, there are two approaches one could take to computing logarithms in G:

  • 1. Use a “square-root” algorithm directly in G, such as Pollard’s rho algorithm (Algorithm 3.60). The miming time of this approach is O(ffq).
  • 2. Let 7 be a generator of Zp, and let l = (p - 1 )/q. Use an index-calculus algorithm in Z* to find integers у and г such that a = -yy and 3 = 7*. Then x = logQ 0 = {z/l)(y/l)~l mod q. (Since у and 2 are both divisible by /, y/l and z/l are indeed integers.) The running time of this approach is Lp[|, c] if the number field sieve is used.

Which of the two approaches is faster depends on the relative size of ffq and Lp[|, с].

 
Source
< Prev   CONTENTS   Source   Next >