Using Symmetries and Fast Change of Ordering in the Index Calculus for Elliptic Curves Discrete Logarithm

Jean-Charles Faugère 1, 2 Pierrick Gaudry 3 Louise Huot 2 Guénaël Renault 1, 2
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
3 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : In 2004, an algorithm is introduced to solve the DLP for elliptic curves defined over a non prime finite field Fqn . One of the main steps of this algorithm requires decomposing points of the curve E(Fqn ) 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 23(n1) 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 Fq5 , with q 264, is supposed to be 2160 operations in E(Fq5 ) using generic algorithms compared to 2127 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¨obner basis which provides a better heuristic complexity of the total solving process.
Type de document :
Communication dans un congrès
SCC 2012 - Third international conference on Symbolic Computation and Cryptography, Jul 2012, Castro Urdiales, Spain. pp.113-118, 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00793097
Contributeur : Brigitte Briot <>
Soumis le : jeudi 21 février 2013 - 15:48:52
Dernière modification le : jeudi 22 septembre 2016 - 14:31:31

Identifiants

  • HAL Id : hal-00793097, version 1

Collections

Citation

Jean-Charles Faugère, Pierrick Gaudry, Louise Huot, Guénaël Renault. Using Symmetries and Fast Change of Ordering in the Index Calculus for Elliptic Curves Discrete Logarithm. SCC 2012 - Third international conference on Symbolic Computation and Cryptography, Jul 2012, Castro Urdiales, Spain. pp.113-118, 2012. <hal-00793097>

Partager

Métriques

Consultations de la notice

329