Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields

Jean-Charles Faugère 1, 2 Ludovic Perret 1, 2 Christophe Petit 3 Guénaël Renault 1, 2
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
2 LIP6 - Laboratoire d'Informatique de Paris 6
3 UCL Crypto Group
DICE - MLG - Dispositifs Intégrés et Circuits Electroniques Machine Learning Group
Abstract : The goal of this paper is to further study the index calculus method that was first introduced by Semaev for solving the ECDLP and later developed by Gaudry and Diem. In particular, we focus on the step which consists in decomposing points of the curve with respect to an appropriately chosen factor basis. This part can be nicely reformulated as a purely algebraic problem consisting in finding solutions to a multivariate polynomial $f (x1 , . . . , xm ) = 0$ such that $x_1 , . . . , x_m$ all belong to some vector subspace of $F_2^n /F_2$ . Our main contribution is the identification of particular structures inherent to such polynomial systems and a dedicated method for tackling this problem. We solve it by means of Gröbner basis techniques and analyze its complexity using the multi-homogeneous structure of the equations. A direct consequence of our results is an index calculus algorithm solving ECDLP over any binary field $F_2^n$ in time $O(2^{ω t} )$, with $t ≈ n/2$ (provided that a certain heuristic assumption holds). This has to be compared with Diem's [14] index calculus based approach for solving ECDLP over Fqn which has complexity exp O(n log(n)1/2 ) for q = 2 and n a prime (but this holds without any heuristic assumption). We emphasize that the complexity obtained here is very conservative in comparison to experimental results. We hope the new ideas provided here may lead to efficient index calculus based methods for solving ECDLP in theory and practice.
Type de document :
Communication dans un congrès
Eurocrypt 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Apr 2012, Cambridge, United Kingdom. Springer, 7237, pp.27-44, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-29011-4_4〉
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00776066
Contributeur : Ludovic Perret <>
Soumis le : lundi 14 janvier 2013 - 23:02:35
Dernière modification le : vendredi 23 novembre 2018 - 08:55:18
Document(s) archivé(s) le : lundi 15 avril 2013 - 04:09:07

Fichier

MAYA2-UPMCINRIA-aaec_1.0.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | LIP6 | UPMC | INRIA-ROCQ | SORBONNE-UNIVERSITE

Citation

Jean-Charles Faugère, Ludovic Perret, Christophe Petit, Guénaël Renault. Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields. Eurocrypt 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Apr 2012, Cambridge, United Kingdom. Springer, 7237, pp.27-44, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-29011-4_4〉. 〈hal-00776066〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

813

Téléchargements de fichiers

368

Contact


archive-ouverte@inria.fr