Paper 2016/003

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
cryptanalysissummation polynomialsalgebraic attacksblock ciphersGr"obner basesDL problemfinite fieldselliptic curvesECDSAgeneric group model
Contact author(s)
n courtois @ cs ucl ac uk
History
2016-01-06: last of 2 revisions
2016-01-04: received
See all versions
Short URL
https://ia.cr/2016/003
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/003,
      author = {Nicolas T.  Courtois},
      title = {On Splitting a Point with Summation Polynomials in Binary Elliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2016/003},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/003}},
      url = {https://eprint.iacr.org/2016/003}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.