Using Symmetries in the Index Calculus for Elliptic Curves Discrete Logarithm
In 2004, an algorithm is introduced to solve the DLP for elliptic curves defined over a non-prime finite field \(\mathbb{F}_{q^{n}}\). One of the main steps of this algorithm requires decomposing points of the curve \(E(\mathbb{F}_{q^{n}})\) with respect to a factor base, this problem is denoted PDP. In this paper, we will apply this algorithm to the case of Edwards curves, the well-known family of elliptic curves that allow faster arithmetic as shown by Bernstein and Lange. More precisely, we show how to take advantage of some symmetries of twisted Edwards and twisted Jacobi intersections curves to gain an exponential factor 2 ?(n?1) to solve the corresponding PDP where ? is the exponent in the complexity of multiplying two dense matrices. Practical experiments supporting the theoretical result are also given. For instance, the complexity of solving the ECDLP for twisted Edwards curves defined over \(\mathbb{F}_{q^{5}}\), with q?264, is supposed to be ? 2160 operations in \(E(\mathbb{F}_{q^{5}})\) using generic algorithms compared to 2130 operations (multiplications of two 32-bits words) with our method. For these parameters the PDP is intractable with the original algorithm.
index calculus elliptic curves edwards curves jacobi intersections curves ecdlp decomposition attack grbner basis with symmetries