10[1]椭圆曲线与群代数

Index calculus for abelian varieties and the elliptic curve discrete logarithm problem Pierrick Gaudry Laboratoire LIX, E´cole polytechnique, France gaudry@lix.polytechnique.fr October 26, 2004 Abstract. We propose an index calculus algorithm for the discrete logarithm problem on gen- eral abelian varieties. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve all elliptic curve discrete logarithm problems defined over Fq3 in time O(q4/3), with a reasonably small constant; and an elliptic problem over Fq4 or a genus 2 problem over Fq2 in time O(q 3/2) with a larger constant. 2000 Mathematics Subject Classification. Primary 11Y16; Secondary 11T71, 94A60. 1 Introduction The elliptic curve discrete logarithm problem is the key stone of the security of many cryp- tosystems [16, 20]. Except for a few families of weak curves [18, 27, 22, 25], the best known algorithms are generic algorithms, like Pollard’s Rho algorithm [21] and its parallel variants [30]. Some attempts have been made to lift the problem, either to Q, like in the Xedni algo- rithm [14, 26, 15], or to a local field [10]. None of them proved to be feasible. A more successful attack was based on the Weil restriction process [11, 7, 2, 13]: taking as input a discrete loga- rithm problem in an elliptic curve defined over an extension field, it is possible to transport it into the Jacobian of a curve of larger genus, but defined over a smaller base field than the initial field. Since there exist sub-exponential algorithms for discrete logarithms in Jacobians of high genus curves [1, 8, 6], in some cases this yields a faster attack than Pollard’s Rho [19, 17]. Recently, Semaev posted two new attempts [23, 24] to solve the discrete logarithm problem on elliptic curves. Although they do not directly lead to complete algorithms, these papers are intriguing. In the present paper, we show that ideas taken from [24], mixed with a Weil restriction approach, combine into an algorithm that can solve the discrete logarithm on elliptic curves defined over small extension fields asymptotically faster than Pollard’s Rho. In particular, we shall demonstrate that a discrete log problem defined over a finite field of the form Fq3 can be solved in time O(q4/3), which has to be compared with O(q3/2) for Pollard’s Rho. To obtain this complexity, we also make use of The´riault’s large prime variant for low genus index calculus [28], and its improvement [12]. The paper is organized as follows: we start with an introductory example that explains an index calculus algorithm solving an elliptic curve discrete logarithm problem over Fp2 in time O(p), which is the same complexity as Pollard’s Rho. In Section 3, we give a general method to solve a discrete logarithm problem on an abelian variety. Then in Section 4, we use the 2 Pierrick Gaudry Weil restriction method to apply our method to elliptic curves defined over extension fields. In that section, we shall see that Semaev’s summation polynomials simplify the formulae. In Section 5, we compare our method to the classical Weil descent attack, from a theoretical and practical point of view. Finally in Section 6, we apply our attack to hyperelliptic curves. 2 Introductory example: elliptic curves over Fp2 Let p = 1019. Then the polynomial f(t) = t2 +1 is irreducible over Fp, and therefore Fp2 can be defined as Fp[t]/(t2 + 1). Let E be the elliptic curve defined over Fp2 by y2 = x3 + ax+ b, where a = a0 + a1t = 214 + 364t, b = b0 + b1t = 123 + 983t. It is easily checked that the group order of E is the prime N = 1039037. Let P be a random generator of E and Q a random point in E. For instance, take P = (401 + 517t, 885 + 15t), and Q = (935 + 210t, 740 + 617t). We define a factor base F for E to be the set of points of E that have an abscissa defined over Fp. It has 1011 elements. Let us form random linear combinations of P and Q and test if they can be written as the sum of two points in F . For instance, let R be the point R = 459328P + 313814Q = (415 + 211t, 183 + 288t). Let P1 = (x1, y1) and P2 = (x2, y2) be two points in F such that R = P1 + P2. In [24], Semaev gives an explicit polynomial f3 called a summation polynomial such that the equality R = P1 + P2 implies that f3(x1, x2, xR) = 0. Rewriting it in terms of e1 = x1 + x2 and e2 = x1x2, we get (e21 − 4e2)x2R − 2(e1e2 + ae1 + 2b)xR + a2 + e22 − 2ae2 − 4be1 = 0. This equation relates quantities in Fp2 and the only unknowns are e1 and e2 that are required to be in Fp. In order to convert this last requirement into an algebraic relation, we use the Weil restriction process, that is we explicitly have t enter the game. Hence, after reducing modulo f(t), we obtain (881e21 + 597e1e2 + 31e1 + 843e2 +669) t+ (329e 2 1 + 189e1e2 + 971e1 + e 2 2 +294e2 +740) = 0. For this equation to be verified, both coefficients in t must be zero. Therefore, we obtain two equations in two indeterminates over Fp. Solving this system via resultants or Gro¨bner basis, we find the following possible value for (e1, e2): (e1, e2) = (845, 1003). And for this pair, we solve (x− x1)(x− x2) = x2 − e1x + e2. The solution we find is x1 = 92 and x2 = 753. Index calculus for abelian varieties and the elliptic curve discrete logarithm problem 3 Then y1 and y2 are easily deduced, and we find P1 = (92, 779 + 754t) and P2 = (753, 628 + 692t). After having produced 1012 such relations, we can solve a linear algebra problem to get a non-trivial combination of P and Q that is zero, and the discrete logarithm of Q in base P follows (we find logP (Q) = 76982). In the main body of the paper, we will show that #F is always of size about p, and that on average we obtain one relation for every two linear combinations of P and Q that we try. Therefore, the matrix of relations can be computed in time O(p) up to logarithmic factors in p. Solving the linear system could be done using general sparse linear algebra tools like Lanczos’s or Wiedemann’s algorithms at a quadratic cost O(p2). In fact, since in each row we have only two non-zero entries, each step within the Gaussian elimination will maintain this sparseness. Hence it can be shown that the running time of the linear algebra step is in O(p). We refer to [9] to a precise analysis of this ultra-sparse linear algebra, based on a graph interpretation. Hence we have found an index-calculus algorithm that has the same complexity as Pollard- Rho up to logarithmic factors, namely O(p) operations, but requires much more memory. In the remainder of the paper, we shall formalize a generalization of this algorithm to abelian varieties, and we shall apply it to curves over Fqn using Weil descent and analyze it for small values of n ≥ 3. 3 An index calculus algorithm for abelian varieties 3.1 A convenient representation of abelian varieties Let A be an abelian variety of dimension n, that is defined over a finite field Fq with q elements. We shall work with an explicit embedding of a dense Zariski-open subspace of A into an affine space of dimension n+m. In other word word文档格式规范word作业纸小票打印word模板word简历模板免费word简历 s, an element P ∈ A will be represented by n + m coordinates P = (x1, . . . , xn, y1, . . . , ym), where xi and yi are in Fq, and such a representation is possible for all the elements of A but a negligible proportion. Furthermore, we assume that for each choice of x1, . . . , xn in Fq, there exist only finitely many m-uples y1, . . . , ym in Fq such that these m + n coordinates yield a point of A. In the case of dimension 1 where A is an elliptic curve, we can take for x1 the classical abscissa coordinate and for yi the ordinate. All the points except the point at infinity can be represented with these two coordinates. In the case where A is the Jacobian of a hyperelliptic curve, we can take for xi the coefficients of the first polynomial in Mumford representation and for yi the coefficients of the second polynomial. For general abelian varieties, no choice seems to be canonical, but usually the way A is constructed and its explicit group law already use such a coordinate system. Note also that a coordinate system with these properties is called a Noether normalization of the variety (see [5]). The coordinates (xi, yi) of a point of A verify some equations that can be assumed to form a triangular set: the first equation is a polynomial in y1 and the xi, the second equation is a polynomial in y1, y2 and the xi, and so on until the last equation which is a polynomial in all the coordinates. Such a triangular system makes explicit the fact that for each value of 4 Pierrick Gaudry xi, there exist only finitely many m-uples for the yi. This system has m equations and they locally define the variety A. In the following, we assume that we are given a discrete logarithm problem to solve in an abelian variety for which this convenient representation is known (Noether normalization and triangular set), together with maps for the group law in this coordinate system. We shall be interested in the complexity in q only, therefore in our estimates, the parameters n, m and the degrees of the equations describing A are supposed to be constant. Remark 1. For an abelian variety given by any set of equations, building a “convenient rep- resentation” reduces to the computation of a Gro¨bner basis. More precisely, we take n coor- dinates that are random linear transformations of the original coordinates. With high prob- ability these new coordinates can be the xi in the Noether normalization. Then computing the triangular set is exactly the computation of a Gro¨bner basis for the lexicographical order of the equations defining A. Considered over the rational function field Fq(x1, . . . , xn), the corresponding ideal is of dimension 0. In [3], it is shown that testing if the dimension of an ideal is zero, and if this is the case, computing a Gro¨bner basis of it can be done in a number of operations in the base field that depends only on the number of equations, their degree and the number of indeterminates. Hence, in our case, where we are only interested in the complexity in q, the runing time is polynomial in log q. Note that the bounds in the reference [3] are not the best known, but the case of positive characteristic is explicitly included, which is required for our application. 3.2 Definition of a factor base Among all the points of A that can be represented in our coordinate system, we shall select some of them to form a factor base. We define the factor base F to be F = {P ∈ A ∩H2 ∩H3 ∩ · · · ∩Hn ; P defined over Fq}, where Hi is the hyperplane of equation xi = 0. Then F = {(x1, 0, . . . , 0, y1, . . . , ym) ∈ A ; x1, yi ∈ Fq} is an algebraic variety (intersection of algebraic varieties) of dimension 1, since y1, . . . , ym are algebraic over x1, which is free. This is therefore a non-empty union of curves. The number of curves and their genus can be bounded independently of q using the degrees of the yi in the triangular set of equations for A. In the following, we shall assume for simplicity that F is irreducible (that is very likely, since A is irreducible), so that by Weil’s bound we have #F = q + O(√q). Otherwise, we have #F = Nq+O(√q), where N is the number of curves, and the formulae below should be modified accordingly. In the end, since N is a constant, it will anyway be swallowed in the O() notation. In the sequel, we shall also need the fact that the closure of F is not included in a strict abelian subvariety of A; this could occur when A is not simple. If this is not the case, this will be easily detected during the algorithm, since the event of a successful decomposition (see below) will occur with a probablity that is very much biased compared to the theory; we then make a random affine transformation of the xi coordinates, and we try again with the corresponding new F (with high probability, F will be suitable). Index calculus for abelian varieties and the elliptic curve discrete logarithm problem 5 3.3 Decomposing a point on the factor base We want to address the following question: Let P be a point on A. Are there points P1, P2, . . . , Pn in F such that P = P1 + P2 + · · ·+ Pn, and how to compute all the solutions? Let Sn be the n-th symmetric group. We introduce the map f from Fn/Sn to A defined by f : (P1, . . . , Pn) �→ P1 + · · ·+ Pn. Since F is not included in a proper abelian subvariety of A, the dimension of the image of f in A is n. Hence for a generic point P in A, the number of preimages by f over the algebraic closure of Fq is finite. We now make this explicit. The group law on A is defined by rational fractions in terms of the coordinates we use. Then there exist n + m explicit rational fractions ϕ1, . . . , ϕn+m such that P1 + · · ·+ Pn = (ϕ1(P1, . . . , Pn), . . . , ϕn+m(P1, . . . , Pn)). Writing the equations corresponding to this (m + n)-uple being equal to P and also the equations describing the fact that all the points are indeed on A or in F , we get a system with more equations than unknowns (i.e. the coordinates of P1,. . . , Pn). The system is (generically) of dimension 0, since it has a finite number of solutions over Fq. For a given P , finding all the solutions P1, . . . , Pn defined over Fq, can be done by a Gro¨bner basis computation, followed by the factorization of a univariate polynomial. The degree of that polynomial is bounded by the degree of the ideal defined by all the equations that were in the system. As already mentionned in the remark 1, the complexity of checking that the ideal is of dimension 0 and of computing the Gro¨bner basis is polynomial in the size of Fq, and some parameters of the system that depend essentially on the degrees of the equations defining A (see [3]). In general, these parameters are at least exponential in n. Remark 2. The rational fractions ϕ1, . . . , ϕn+m are usually valid only locally. For instance, evaluated at points with P1 = P2, one of them could degenerate into 0/0; just like for elliptic curves where the doubling formula is distinct from the adding formula. Averaged over all the points P in A, this non-universality of the rational fractions will make us lose a negligible quantity of decomposable points. 3.4 Index calculus computation Let P be a point on A and let Q be another point that is a multiple of P . The goal is to compute the discrete logarithm of Q in base P . Let a and b be random integers bounded by the order of P . We form the linear combination R = aP +bQ, and we try to decompose it on the factor base using the Gro¨bner basis approach of the previous paragraph. If we get a solution, we store it as a relation. It is possible that there are several solutions for a single R. In that case, we just get more relations for the same effort. After having collected more relations than the cardinality of the factor base F , a linear algebra elimination on the relations allows to generate a hopefully non-trivial linear combi- nation between P and Q that is zero in A. The discrete logarithm is deduced readily. 6 Pierrick Gaudry Remark 3. If P does not generate the whole abelian variety A, then R is no longer a random point in A, and the estimates below are not valid. Using classical randomization techniques as in [6], this is not a problem, as long as the group structure of A is explicitly known. 3.5 Expected number of collected relations — Overall complexity The key issue is how likely it is to find a relation. When decomposing a point P in A, we are precisely computing the preimages f−1(P ) where f is the function defined above. The expected number of elements in f−1(P ) is then ∑ P∈A #f−1(P ) #A = 1 #A #(Fn/Sn). Estimating that #A ≈ qn, we obtain that the expected number of relations produced by each trial is 1/n!. This factorial is not a surprise, since in the classical Weil descent attack, a g! factor occurs in the complexity. The complexity of the algorithm can now be deduced, at least if one assumes that the parameters of A are fixed and q tends to infinity. Indeed, as mentioned above, the point decomposition can be done in polynomial time in log q. The average number of obtained relations is in 1/n! which is a constant, so that we need O(q) operations to collect the relations and then O(q2) steps to solve the linear algebra problem. This has to be compared with the complexity of the Pollard-Rho method which is in O(qn/2). Obviously, The´riault’s algorithm [28] and its improvements [12] to index-calculus on small genus curves also apply in our context. Hence we obtain a complexity of O(q2− 2 n ), so that for n = 3, we get O(q4/3) instead of O(q3/2) with Pollard Rho. We insist on the fact that the constant hidden in the O() is big and grows very fast with n. We shall estimate it more precisely in the framework of the Weil descent of elliptic curves in the next section. Theorem 1. Let A be an abelian variety of dimension n over Fq given by explicit equations. Then there exists a probabilistic algorithm that can solve discrete logarithm problems in A in time O(q2− 2 n ) up to logarithmic factors in q and where the constant depends (badly) on n. 4 Application to elliptic curves Let E be an elliptic curve defined over a finite field Fqn , where q is a prime or a prime power. Then, using the Weil descent approach, a discrete logarithm problem on E can be viewed as a discrete logarithm problem on an abelian variety of dimension n over Fq. We thus obtain the following result: Theorem 2. Let n be a fixed integer and let q be a prime or a prime power that we let grow to infinity. There exists an algorithm that can solve a discrete logarithm problem on any elliptic curve defined over a finite field with qn elements in time O(q2− 2 n ) up to logarithmic factors in q and where the constant depends on n. Index calculus for abelian varieties and the elliptic curve discrete logarithm problem 7 We shall show below that the constant hidden in the O() grows very fast with n and only small degree extensions are vulnerable to this attack. Note that since we allow the base field to be a non-prime field, if the degree of the extension is composite, one can consider it as an extension of an intermediate subfield in order to keep n small. In the remainder of this section, we give more details on the application to elliptic curves. In particular we show how Semaev’s summation polynomials make the Gro¨bner basis a little more explicit, thus allowing to analyze the dependance in n of the complexity. For simplicity, we restrict to the case where the characteristic is larger than 3. Otherwise, the equations should be adapted accordingly. 4.1 Semaev’s summation polynomials We recall here the definition and properties of the summation polynomials introduced by Semaev [24]. Definition 1. Let E be an elliptic curve of equation y2 = x3 + ax + b. The summation polynomials fn of E are defined by the following recurrence. The initial values for n = 2 and n = 3 are given by f2(X1,X2) = X1 −X2 and f3(X1,X2,X3) = (X1−X2)2X23−2((X1+X2)(X1X2+a)+2b)X3+((X1X2−a)2−4b(X1+X2)), and for n ≥ 4 and 1 ≤ k ≤ n− 3, fn(X1, . . . ,Xn) = ResX(fn−k(X1, . . . ,Xn−k−1,X), fk+2(Xn−k, . . . ,Xn,X)). Semaev proves that the apparent redundancy in the definition of fn via different values of k is consistent. The raison d’eˆtre of these polynomials is the following result that relates fn to the group law on E. Theorem 3. Let E/k be an elliptic curve, n ≥ 2 an integer and fn its n-th summation polynomial. Let x1, . . . , xn be n elements of an algebraic closure k of k. Then fn(x1, . . . , xn) = 0 if and only if there exists a n-tuple (y1, . . . , yn) in k, such that for all i, Pi = (xi, yi) is a point of E and P1 + · · ·+ Pn = 0. Furthermore, if n ≥ 3, the polynomial fn is symmetric of degree 2n−2 in each variable. 4.2