TY - GEN
T1 - Improving the complexity of index calculus algorithms in elliptic curves over binary fields
AU - Faugère, Jean Charles
AU - Perret, Ludovic
AU - Petit, Christophe
AU - Renault, Guénaël
PY - 2012/4/26
Y1 - 2012/4/26
N2 - 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(x 1,.,x m )=0 such that x 1,.,x m all belong to some vector subspace of F 2/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 2nin time O(2 wt ) , 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 F qn which has complexityexp (nlog(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.
AB - 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(x 1,.,x m )=0 such that x 1,.,x m all belong to some vector subspace of F 2/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 2nin time O(2 wt ) , 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 F qn which has complexityexp (nlog(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.
KW - Elliptic Curve Cryptography
KW - Index Calculus
KW - Polynomial System Solving
U2 - 10.1007/978-3-642-29011-4_4
DO - 10.1007/978-3-642-29011-4_4
M3 - Conference contribution
AN - SCOPUS:84860003880
SN - 9783642290107
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 27
EP - 44
BT - Advances in Cryptology, EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
T2 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2012
Y2 - 15 April 2012 through 19 April 2012
ER -