International Association
for Cryptologic Research

Recent research for efficient algorithms for solving the discrete logarithm (DL) problem on elliptic curves depends on the difficult question of the feasibility of index calculus which would consist of splitting EC points into sums of points lying in a certain subspace. A natural algebraic approach towards this goal is through solving systems of non-linear multivariate equations derived from the so called summation polynomials which method have been proposed by Semaev in 2004.

In this paper we consider a simple variant of this problem with splitting in two in binary curves. We propose an algorithm with running time of the order of 2^{n/3} for this problem. This property clearly violates the generic group assumption for these curves.