**Using Symmetries in the Index Calculus for Elliptic Curves Discrete Logarithm**

*Jean-Charles Faugère and Pierrick Gaudry and Louise Huot and Guénaël Renault*

**Abstract: **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^{\omega (n-1)}\) to solve the corresponding PDP where $\omega$ 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 $\F_{q^5}$, with
\(q\approx2^{64}\), is supposed to be $\sim$ $2^{160}$ operations in
$E(\F_{q^5})$ using generic algorithms compared to \(2^{130}\)
operations (multiplication of two $32$-bits words) with our
method. For these parameters the PDP is intractable with the original
algorithm.

The main tool to achieve these results relies on the use of the symmetries and the quasi-homogeneous structure induced by these symmetries during the polynomial system solving step. Also, we use a recent work on a new algorithm for the change of ordering of Gröbner basis which provides a better heuristic complexity of the total solving process.

**Category / Keywords: **public-key cryptography / ECDLP, Index Calculus, Gröbner Basis with symmetries

**Date: **received 12 Apr 2012, last revised 18 Jun 2013

**Contact author: **louise huot at lip6 fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20130618:120620 (All versions of this report)

**Short URL: **ia.cr/2012/199

[ Cryptology ePrint archive ]