International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 13 April 2012

Jean-Charles Faugère, Pierrick Gaudry, Louise Huot, Guénaël Renault
ePrint Report ePrint Report
In 2004, an algorithm is introduced to solve the DLP for elliptic

curves defined over a non prime finite field $\\F_{q^n}$. One of the

main steps of this algorithm requires decomposing points of the curve

$E(\\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^{3 (n-1)}$ to solve the corresponding PDP. Practical experiments

supporting the theoretical result are also given. For instance, the

complexity of solving the ECDLP for twisted Edwards curves defined

over $\\F_{q^5}$, with $q\\approx2^{64}$, is supposed to be $2^{160}$

operations in $E(\\F_{q^5})$ using generic algorithms compared to

$2^{127}$ operations (multiplication of two $32$ bits words) with

our method. For these parameters the PDP is untractable with the

original algorithm.

The main tool to achieve these results relies on the use of the

symmetries during the polynomial system solving step. Also, we use a

recent work on a new strategy for the change of ordering of Gröbner

basis which provides a better heuristic complexity of the total

solving process.

Expand

Additional news items may be found on the IACR news page.