Cryptology ePrint Archive: Report 2015/319
Point Decomposition Problem in Binary Elliptic Curves
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: ia.cr/2015/319
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]