**On Splitting a Point with Summation Polynomials in Binary Elliptic Curves**

*Nicolas T. Courtois*

**Abstract: **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 [12].
In this paper we consider simplified variants of this problem with splitting in two or three parts in binary curves. We propose three algorithms with running time of the order of 2^n/3 for both problems. It is not clear how to interpret these results but they do in some sense violate the generic group model for these curves.

**Category / Keywords: **public-key cryptography / cryptanalysis, summation polynomials, algebraic attacks, block ciphers, Gr"obner bases, DL problem, finite fields, elliptic curves, ECDSA, generic group model

**Date: **received 3 Jan 2016, last revised 5 Jan 2016

**Contact author: **n courtois at cs ucl ac uk

**Available format(s): **PDF | BibTeX Citation

**Version: **20160106:003159 (All versions of this report)

**Short URL: **ia.cr/2016/003

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]