Speeding up Simultaneous Scalar Multiplication on Elliptic Curves
Scalar multiplication is the basic and most expensive operation in elliptic curve based cryptographic protocols. It is the computation of integer multiple of a given point on the curve. Computation of scalar multiple is faster by using signed binary representation as compared to binary representation. Direct- recoding is a new and efficient algorithm for computation of signed binary representation as compared to the existing methods like NAF, MOF and complementary recoding. In this paper, we propose a novel method for speeding up simultaneous scalar multiplication using direct recoding method.
Keywords: Elliptic curve cryptography, simultaneous scalar multiplication, signed binary method, NAF, MOF, complementary recoding, JSF
Diffie, W., Hellman, M.E.: New Directions in Cryptography, IEEE Transactions on
Information Theory, IT-22, 644–654 (1976)
Rivest, R.L., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and
Public-key Cryptosystems. Communications of the ACM 21, 120–126 (1978)
V. S. Miller, Use of elliptic curves in cryptography, Advances in Cryptology, Proceedings of
CRYPTO'85, LNCS, 218 (1986), 417-426.
N. Koblitz, Elliptic curve cryptosystem, Mathematics of Computation, 48 (1987) 203-209.
Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Huanguo
Zhang, Publishing House of Electronics Industry, pp. 74–76 (2005)
Standard Specifications for Public Key Cryptography, IEEE Standard 1363, 2000.
A.D. Booth, A signed binary multiplication technique, Journal of Applied Mathematics, 4(2)
G. W. Reitwiesner, Binary Arithmetic, Advances in computers, 1 (1960), 231-308.
Gordon, D.M.: A survey of fast exponentiation methods. Journal of Algorithms 27, 129–146
F. Morain, J.Olivos, Speeding up the computations on an elliptic curve using addition
subtraction chains, RAIRO Theoretical Informatics and Applications, 24 (1990), 531-543.
K. Okeya, Signed binary representations revisited, Proceedings of CRYPTO'04 (2004), 123-
M. Joye, S. Yen, Optimal left to right binary signed digit recoding, IEEE Transactions on
Computers, 49 (2000), 740-748.
H.K.Pathak, Manju Sanghi, Speeding up Computation of Scalar Multiplication in
Elliptic Curve Cryptosystem, Journal on computer science and engineering, 2, (2010), 1024-
P.Balasubramaniam, E. Karthikeyan, Fast Simultaneous scalar multiplication, Applied
Mathematics and Computation, 192 (2007), 399-404.
J.A. Solinas, Low-weight binary representations for pairs of integers, Technical Report
CORR 2001-41, Center for Applied Cryptographic Research, University of Waterloo,
- There are currently no refbacks.