Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem (Q733510)

The present paper proposes an index calculus algorithm for computing the discrete logarithm problem (DLP) on abelian varieties and deduces an algorithm for the DLP on elliptic curves defined over small extensions fields, which is asymptotically faster than Pollard's rho method. Section 2 begins specifying the type of abelian variety to which the method applies: an abelian variety \(A\)\, of (small) dimension \(n\),\, defined over a finite field \(\mathbb F_q\),\, together with an explicit embedding of (a dense Zariski open of) \(A\)\, into an affine space of dimension \(n+m\). Also the points \(P=(x_1, \dots , x_n, y_1, \dots y_m)\in A\)\, are supposed to verify a triangular system of \(m\) equations. As the paper points out this definition covers the cases usually considered in Cryptography, as Jacobians of curves and Weil restrictions of them. Then Section 2 describes the algorithm, whose factor base is defined as the set of points \({\mathcal F}=\{(x_1,0,\dots, 0,y_1,\dots ,y_m)\in A;\,\, x_1,y_i\in\mathbb F_q \}\),\, assumed to be an absolutely irreducible curve and studies its complexity. If the parameters \(n,m\)\, and the degrees of the equations defining \(A\)\, are supposed to be constants, the ``Heuristic result 3'' says that for \(n\geq 2\)\, the asymptotic complexity is \(\widetilde{O}(q^{2-2/n})\). Section 3 applies the proposed algorithm to elliptic curves defined over \(\mathbb F_{q^n}\)\,,\, (\(n\)\, small). Using the Weil restriction approach and the summation polynomials of \textit{I. Semaev} [Preprint, \url{http://eprint.iacr.org/2004/031} (2004)], the paper obtains (Heuristic result 4) a probabilistic algorithm to solve the DLP on such a curve in heuristic time \(\widetilde{O}(q^{2-2/n})\). It also shows an explicit example in the case \(n=2\). Section 4 compares the above algorithm with the classical Weil descent attack [see \textit{P. Gaudry}, \textit{F. Hess} and \textit{N. P. Smart}, J. Cryptology 15, No. 1, 19--46 (2001; Zbl 0996.94036)], summarizing the advantages and inconveniences of the proposed method. Finally Section 5 studies how the algorithm can applied to hyperelliptic curves. In particular. for \(n=1\)\, the paper shows that the classical index calculus algorithm on the Jacobian of the curve [\textit{L. M. Adleman, J. DeMarrais, M.-D. Huang}, Algorithmic number theory. 1st international symposium, ANTS-I, Lect. Notes Comput. Sci. 877, 28--40 (1994; Zbl 0829.11068)], can be seen as a particular case of the present algorithm.