TY - GEN
T1 - Symmetrized summation polynomials
T2 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2014
AU - Faugère, Jean Charles
AU - Huot, Louise
AU - Joux, Antoine
AU - Renault, Guénaël
AU - Vitse, Vanessa
PY - 2014/1/1
Y1 - 2014/1/1
N2 - 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.
AB - 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.
KW - ECDLP
KW - Semaev polynomials
KW - decomposition method
KW - elliptic curves
KW - index calculus
KW - invariant theory
KW - multivariate polynomial systems
UR - https://www.scopus.com/pages/publications/84901675900
U2 - 10.1007/978-3-642-55220-5_3
DO - 10.1007/978-3-642-55220-5_3
M3 - Conference contribution
AN - SCOPUS:84901675900
SN - 9783642552199
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 40
EP - 57
BT - Advances in Cryptology, EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
PB - Springer Verlag
Y2 - 11 May 2014 through 15 May 2014
ER -