×

Fast elliptic curve point multiplication based on binary and binary non-adjacent scalar form methods. (English) Zbl 1408.94939

Summary: This article presents two methods for developing algorithms of computing scalar multiplication in groups of points on an elliptic curve over finite fields. Two new effective algorithms have been presented: one of them is based on a binary Non-Adjacent Form of scalar representation and another one on a binary of scalar representation method. All algorithms were developed based on simple and composite operations with point and also based on affine and Jacobi coordinates systems taking into account the latest achievements in computing cost reduction. Theorems concerning their computational complexity are formulated and proved for these new algorithms. In the end of this article comparative analysis of both new algorithms among themselves and previously known algorithms are represented.

MSC:

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
14G50 Applications to coding theory and cryptography of arithmetic geometry
14H52 Elliptic curves
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Avanzi, R., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press (2005) · Zbl 1082.94001
[2] ANSI X9.62:2005, Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA), Accredited Standards Committee on Financial Services, X9 (2005)
[3] Billet, O., Joye, M.: Fast Point Multiplication on Elliptic Curves through Isogenies, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, LNCS vol. 2643, pp. 43-50. Springer-Verlag (2003) · Zbl 1030.11027
[4] Bosma, W, Signed bits and fast exponentiation, J. Theor. Nombres Bordeaux, 13, 27-41, (2001) · Zbl 1060.11082 · doi:10.5802/jtnb.301
[5] Brown, M., Hankerson, D., Lopez, J., Menezes, A.: Software Implementation of the NIST elliptic curves over prime fields. In: Progress in Cryptology CT-RSA 2001 , LNCS vol. 2020, pp. 250-265. Springer-Verlag (2001) · Zbl 0968.68049
[6] Chudnovsky, D; Chudnovsky, G, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Adv. Appl. Math., 7, 385-434, (1986) · Zbl 0614.10004 · doi:10.1016/0196-8858(86)90023-0
[7] Ciet, M; Joye, M; Lauter, K; Montgomery, P, Trading inversions for multiplications in elliptic curve cryptography, designs, Codes Cryptog., 39, 189-206, (2006) · Zbl 1116.14026 · doi:10.1007/s10623-005-3299-y
[8] Cohen, H., Miyaji, A., Ono, T.: Efficient Elliptic Curve Exponentiation using Mixed Coordinates, Advances in Cryptology - ASIACRYPT ’98, Vol. 1514 of Lecture Notes in Computer Science, pp. 51-65. Springer-Verlag (1998) · Zbl 0939.11039
[9] Dimitrov, V; Imbert, L; Mishra, PK, Efficient and secure elliptic curve point multiplication using double-base chains, advances in cryptology - ASIACRYPT’05, Lect. Notes Comput. Sci., 3788, 59-78, (2005) · Zbl 1154.94388 · doi:10.1007/11593447_4
[10] Eisentrȧger, K., Lauter, K., Montgomery, P.: Fast elliptic curve arithmetic and improved Weil pairing evaluation, Topics in CryptographyCT-RSA 2003, vol. 2612, Lecture Notes in Computer Science, no. 230, pp. 343354 (2003) · Zbl 1038.11079
[11] Fay, B.: Double-and-add with relative Jacobian coordinates (2014). http://eprint.iacr.org/2014/1014.pdf · Zbl 0622.94015
[12] FIPS PUB 186-2. Digital Signature Standard (DSS). — National Institute of Standards and Technology (NIST), pp. 70 (2000)
[13] Gordon, DM, A survey of fast exponentiation method, J. Algor., 27, 129-146, (1998) · Zbl 0915.11064 · doi:10.1006/jagm.1997.0913
[14] Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer-Verlag (2004) · Zbl 1059.94016
[15] P. IEEE Std 1363-2000. IEEE Standard Specifications for Public-Key Cryptography. The Institute of Electrical and Electronics Engineers (IEEE) (2000) · Zbl 0915.11064
[16] Knuth, D.: The Art of Computer Programming, Semi numerical Algorithms, 3 edn. Addison-Wesley (1998) · Zbl 0895.65001
[17] Koblitz, N, Elliptic curve cryptosystems, Math. Comput., 48, 203-209, (1987) · Zbl 0622.94015 · doi:10.1090/S0025-5718-1987-0866109-5
[18] Longa, P., Miri, A.: Fast and Flexible Elliptic Curve Point Arithmetic over Prime Fields, to appear in IEEE Transactions on Computers (2007). Also available at https://doi.org/10.1109/TC.2007.70815 · Zbl 1374.94794
[19] Longa, P.: Accelerating the Scalar Multiplication on Elliptic Curve Cryptosystems over Prime Fields (2008)
[20] Longa, P.: New Composite Operations and Precomputation Scheme for Elliptic Curve Cryptosystems over Prime Fields (2008) · Zbl 1162.94387
[21] Meloni, N.: Fast and Secure Elliptic Curve Scalar Multiplication over Prime Fields using Special Addition Chains, Cryptology ePrint Archive Report 2006/216 (2006) · Zbl 0614.10004
[22] Miller, V.: Use of Elliptic-Curves in Cryptography, Advances in Cryptology - Crypto ’85, LNCS, vol. 218, pp. 417-426. Springer (1986) · Zbl 0589.94005
[23] NIST PUB 800-57. Recommendation for Key Management Part 1: General (Revision 3). — National Institute of Standards and Technology (NIST), pp. 142 (2012) · Zbl 1060.11082
[24] Okeya, K; Schmidt-Samoa, K; Spahn, C; Takagi, T, Signed binary representations revisited, advances in cryptology - CRYPTO, Lect. Notes Comput. Sci, 3152, 123-139, (2004) · Zbl 1104.94034 · doi:10.1007/978-3-540-28628-8_8
[25] SEC 1: Elliptic Curve Cryptography. Standards for Efficient Cryptography, Certicom Corp., (2009)
[26] Sullivan, N.T.: Fast Algorithms for Arithmetic on Elliptic Curves Over Prime Fields (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.