Symmetrized summation polynomials: using small order torsion points to speed up elliptic curve index calculus

Jean-Charles Faugère 1 Louise Huot 1 Antoine Joux 1 Guénaël Renault 1 Vanessa Vitse 2, 3
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Decomposition-based index calculus methods are currently efficient only for elliptic curves E defined over non-prime finite fields of very small extension degree n. This corresponds to the fact that the Semaev summation polynomials, which encode the relation search (or “sieving”), grow over-exponentially with n. Actually, even their computation is a first stumbling block and the largest Semaev polynomial ever computed is the 6-th. Following ideas from Faugère, Gaudry, Huot and Renault, our goal is to use the existence of small order torsion points on E to define new summation polynomials whose symmetrized expressions are much more compact and easier to compute. This setting allows to consider smaller factor bases, and the high sparsity of the new summation polynomials provides a very efficient decomposition step. In this paper the focus is on 2-torsion points, as it is the most important case in practice. We obtain records of two kinds: we successfully compute up to the 8-th symmetrized summation polynomial and give new timings for the computation of relations with degree 5 extension fields.
Type de document :
Communication dans un congrès
EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2014, Copenhagen, Denmark. Springer, 8441, pp.40-57, 2014, Lecture Notes in Computer Science. <10.1007/978-3-642-55220-5_3>
Liste complète des métadonnées


https://hal.inria.fr/hal-00935050
Contributeur : Guénaël Renault <>
Soumis le : mardi 30 décembre 2014 - 14:09:50
Dernière modification le : mercredi 10 août 2016 - 17:31:42
Document(s) archivé(s) le : samedi 15 avril 2017 - 11:55:13

Fichier

Semaev2torsion.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Charles Faugère, Louise Huot, Antoine Joux, Guénaël Renault, Vanessa Vitse. Symmetrized summation polynomials: using small order torsion points to speed up elliptic curve index calculus. EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2014, Copenhagen, Denmark. Springer, 8441, pp.40-57, 2014, Lecture Notes in Computer Science. <10.1007/978-3-642-55220-5_3>. <hal-00935050>

Partager

Métriques

Consultations de
la notice

365

Téléchargements du document

246