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 is worth.

Category / Keywords: public key cryptography / elliptic curve discrete logarithm problem, point decomposition problem

Date: received 8 Apr 2015, last revised 17 Apr 2015

Contact author: kkarabina at fau edu

Available format(s): PDF | BibTeX Citation

Note: Refrence [6] is added.

Version: 20150418:044805 (All versions of this report)

Short URL: ia.cr/2015/319

Discussion forum: Show discussion | Start new discussion