ANALYSIS ON THE ELLIPTIC SCALAR MULTIPLICATION USING INTEGER SUB-DECOMPOSITION METHOD
Ruma Kareem K. Ajeena, Hailiza Kamarulhaili · International Journal of Pure and Apllied Mathematics · 2013
This study proposes a new approach called, integer sub-decomposition (ISD), to compute any multiple kP of a point P of order n lying on an elliptic curve.Our method depends, in computations, on fast endomorphisms ψ 1 and ψ 2 of elliptic curve over prime fields.The integer sub-decomposition to multiple kP , when the value of k is decomposed into two values k 1 and k 2 , where both values or one of them is not bounded by ±C √ n, is illustrated in the following formula:where -C √ n < k 11 , k 12 , k 21 , k 22 < C √ n.The integers k 11 , k 12 , k 21 and k 22 are computed by solving a closest vector problem in lattice.Consequently, as for this sub-decomposition, we have managed to increase the percentage of a successful computation of kP .Moreover, the gap in the proof of the bound of kernel K vectors of the reduction map T : (a, b) → a + λb(mod n) on ISD method will be filled through the analysis of the multiplier k, using two fast endomorphisms with minimal polynomials X 2 + rX i + s i for i = 1, 2, 3.In particular, we prove an integer sub-decomposition (ISD) with explicit constant kP = k 11 P + k 12 ψ 1 (P ) + k 21 P + k 22 ψ 2 (P ), with max{|k 11 |, |k 12 |} and max{|k 21 |, |k 22 |} < 1 + |r i | + s i √ n , for i = 1, 2, 3.