Authors 
: 

Document type 
: 
Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection

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 x1, . . . , xm all belong to some vector
subspace of F2n/F2. 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
F2n in time O(2w 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
expO(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. 
Access type 
: 
Accès restreint 
Publication date 
: 
2012 
Language 
: 
Anglais 
Conference 
: 
"31st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2012)", Cambridge (UK) (du 15/04/2012 au 19/04/2012) 
Peer reviewed 
: 
yes 
Host document 
: 
"Proceeedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2012)" 2744 
Publisher 
: 
D. Pointcheval and T. Johansson (Eds.) 
Publication status 
: 
Publié 
Affiliations 
: 
INRIA
 Centre ParisRocquencourt UPMC  Université de Paris 06
 INRIA UCL
 SST/ICTM/ELEN  Pôle en ingénierie électrique Université Pierre et Marie Curie LIP6

Keywords 
: 
Elliptic Curve Cryptography ; Index Calculus ; Polynomial System Solving

Links 
: 
