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
-
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},
url = {https://eprint.iacr.org/2015/319}
}
