Open    Access



Upper Bound of Scalars in the Integer Sub-decomposition Method: The Theoretical Aspects




Author(s)

Ruma Kareem K. Ajeena

Full-Text PDF XML     940 Views

DOI:10.17265/2328-2231/2015.02.004

Babylon University, Department of Mathematics, Education College for Pure Sciences, Babil 51002, Iraq

The focal point of this paper is to present the theoretical aspects of the building blocks of the upper bounds of ISD (integer sub-decomposition) method defined by kP  k11 P  k121 (P)  k21 P  k222 (P) with max k11 , k12  C n and max k21 , k22  C n , where C  1 that uses efficiently computable endomorphisms  j for j  1,2 to compute any multiple kP of a point P of order n lying on an elliptic curve E. The upper bounds of sub-scalars in ISD method are presented and utilized to enhance the rate of successful computation of scalar multiplication kP. Important theorems that establish the upper bounds of the kernel vectors of the ISD reduction map are generalized and proved in this work. The values of C in the upper bounds, that are greater than 1, have been proven in two cases of characteristic polynomials (with degree 1 or 2) of the endomorphisms. The upper bound of ISD method with the case of the endomorphism rings over an integer ring Z results in a higher rate of successful computations kP. Compared to the case of endomorphism rings, which is embedded over an imaginary quadratic field Q   D . The determination of the upper bounds is considered as a key point in developing the ISD elliptic scalar multiplication technique.

Elliptic curve cryptography, scalar multiplication, ISD method, efficiently computable endomorphism, upper bounds.