Paper 2015/319

Point Decomposition Problem in Binary Elliptic Curves

Koray Karabina

Abstract

We analyze the point decomposition problem (PDP) in binary elliptic curves. It is known that PDP in an elliptic curve group can be reduced to solving a particular system of multivariate non-linear system of equations derived from the so called Semaev summation polynomials. We modify the underlying system of equations by introducing some auxiliary variables. We argue that the trade-off between lowering the degree of Semaev polynomials and increasing the number of variables provides a significant speed-up.

Note: Minor edits in the text.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Semaev polynomialselliptic curvespoint decomposition problemdiscrete logarithm problem
Contact author(s)
kkarabina @ fau edu
History
2015-10-27: last of 3 revisions
2015-04-11: received
See all versions
Short URL
https://ia.cr/2015/319
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/319,
      author = {Koray Karabina},
      title = {Point Decomposition Problem in Binary Elliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2015/319},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/319}},
      url = {https://eprint.iacr.org/2015/319}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.