Cryptology ePrint Archive: Report 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.

Category / Keywords: Semaev polynomials, elliptic curves, point decomposition problem, discrete logarithm problem

Date: received 8 Apr 2015, last revised 27 Oct 2015

Contact author: kkarabina at fau edu

Available format(s): PDF | BibTeX Citation

Note: Minor edits in the text.

Version: 20151027:143240 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]