Point Decomposition Problem in Binary Elliptic Curves
This work addresses a cryptographic problem for researchers in elliptic curve cryptography, but it appears incremental as it builds on known reduction methods without claiming major breakthroughs.
The authors tackled the point decomposition problem in binary elliptic curves by modifying the system of equations derived from Semaev polynomials with auxiliary variables, arguing that this trade-off between lowering polynomial degree and increasing variables is beneficial.
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.