Details:
Title  Improving the complexity of index calculus algorithms in elliptic curves over binary fields.  Author(s)  Renault Guéna"el, Faug`ere JeanCharles, Ludovic Perret, Christophe Petit  Type  Book, Chapter in Book, Conference Proceeding  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(x 1,…,x m ) = 0 such that x 1,…,x m all belong to some vector subspace of 𝔽2n/𝔽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 multihomogeneous structure of the equations. A direct consequence of our results is an index calculus algorithm solving ECDLP over any binary field 𝔽2n 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 𝔽qn which has complexity exp(O(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.  Keywords  Elliptic Curve Cryptograph Index Calculu Polynomial System Solving  ISBN  9783642290107/pbk 
URL 
http://link.springer.com/chapter/10.1007%2F9783642290114_4 
Language  English  Pages  2744  Publisher  Berlin: Springer  Year  2012  Edition  0  Translation 
No  Refereed 
No 
