Fast Computation Algorithms of Transformations Based on Elliptic Curves with Precomputations

The paper considers efficient algorithms for calculating transformations based on elliptic curves. This new research area is of great interest nowadays. The paper presents an effective scalar multiplication of an elliptic curve point defined over the prime field using of preliminary calculations. The proposed algorithms are based on the method of incompatible representations of the scalar (Non-Adjacent Form, NAF) with a window of both fixed and variable width (a sliding window). In order to evaluate the effectiveness of the previously obtained algorithms we proposed the architecture of the algorithms and the criterion of efficiency based on the average computational complexity. For elaborating newer and more efficient algorithms some effective operations both in the prime field and with a point, such as addition (ADD), doubling (DBL, DBLJ), a complex operation "double and add" (DA), a scaling duplication (SCALE), properties of the affine coordinate system, and Jacobi and Jacobi-Chudnovsky coordinate systems are used. Statements about the algorithms computational complexity are formulated and proved.

References

[1] Hankerson D., Menezes A., Vanstone S. Guide to elliptic curve cryptography. Springer-Verlag, 2004.

[2] Matthieu R. Fast and regular algorithms for scalar multiplication over elliptic curves. IACR Cryptology, 2011, no. 338.

[3] Rokhlin V., Tygert M. Fast algorithms for spherical harmonic expansions. SIAM J. Sci. Computing, 2008, no. 27 (6), pp. 1903-1928.

[4] Hisil H., Carter G., Ed.: Dawson E. New formulae for efficient elliptic curve arithmetic, 2007.

[5] Bernstein Daniel J., Lange T. Explicit-formulas database, 2014. URL: http://hyperelliptic.org/EFD (accessed: 03.01.2015).

[6] Khleborodov D.S. Efficient Algorithms for Scalar Multiplication of an Elliptic Curve Point without Precomputation. Global’nyy nauchnyy potentsial [Global Research Potential], 2014, no. 5 (38). 35 p.

[7] Björn F. Double-and-add with relative Jacobian coordinates. Cryptology, 2014. ePrint Archive.

[8] Bernstein Daniel J., Lange T. Faster addition and doubling on elliptic curves. 2007, pp. 29-50.

[9] Dygin D.M., Grebnev S.V. Efficient implementation of the GOST R 34.10 digital signature scheme using modern approaches to elliptic curve scalar multiplication, 2013.

[10] Edwards H.M. A normal form for elliptic curves. Bulletin of the American Mathematical Society, 2007, no. 44, pp. 393-422. URL: http://www.ams.org/bull/2007-44-03/S0273-0979-07-01153-6/home.html (accessed: 18.03.2015).