Open Access Open Access  Restricted Access Subscription or Fee Access

A Literature Review on Scalar Recoding Algorithms in Elliptic Curve Cryptography


(*) Corresponding author


Authors' affiliations


DOI: https://doi.org/10.15866/irecap.v5i4.5673

Abstract


Elliptic Curve Cryptosystem (ECC) is a type of public key cryptography (PKC) based on the algebraic structure of elliptic curve over finite fields. In mid 80s Neal Koblitz and Victor Miller independently proposed the use of elliptic curves in cryptography. For a smaller key size, ECC is able to provide same level of security with RSA. This feature made ECC one of the most popular PKC algorithms today. Scalar multiplication is known as the fundamental operation in ECC algorithm and protocols. The efficiency of ECC is critically depends on efficiency of scalar multiplication operation. Scalar multiplication involves with three levels of computations: scalar arithmetic, point arithmetic and field arithmetic. Improving the first two levels will lead to significant increment in efficiency of scalar multiplication. Scalar arithmetic level can improve by employing an enhanced scalar recoding algorithm that can reduce the Hamming weight or de-crease the number of operations in the scalar representation process. This paper reviews some of the recoding algorithms and techniques.
Copyright © 2015 Praise Worthy Prize - All rights reserved.

Keywords


Elliptic Curve Cryptosystem; Public Key Cryptography; Scalar Multiplication; Scalar Recoding; Non-Adjacent Form

Full Text:

PDF


References


N. Koblitz, “Elliptic curve cryptosystems,” Math. Comput., vol. 48, no. 177, pp. 203–209, 1987.
http://dx.doi.org/10.1090/s0025-5718-1987-0866109-5

M. Bafandehkar, S. Md Yasin, R. Mahmod, and Z. M. Hanapi, “Comparison of ECC and RSA Algorithm in Resource Constrained Devices,” IT Convergence and Security (ICITCS), 2013 International Conference on. pp. 1–3, 2013.
http://dx.doi.org/10.1109/icitcs.2013.6717816

R. K. Kodali, K. H. Patel, and N. Sarma, “Implementation of Energy Efficient Scalar Point Multiplication Techniques for ECC.,” Int. J. Recent Trends Eng. Technol., vol. 9, no. 1, 2013.

A. Rezai and P. Keshavarzi, “A New Left-to-Right Scalar Multiplication Algorithm Using a New Recoding Technique,” Algorithms, vol. 8, no. 3, 2014.
http://dx.doi.org/10.14257/ijsia.2014.8.3.04

X. Huang, P. G. Shah, and D. Sharma, “Minimizing hamming weight based on 1’s complement of binary numbers over GF (2 m),” in Advanced Communication Technology (ICACT), 2010 The 12th International Conference on, 2010, vol. 2, pp. 1226–1230.

S. U. Nimbhorkar and D. L. G. Malik, “A Survey On Elliptic Curve Cryptography (ECC),” International Journal of Advanced Studies in Computers, Science and Engineering, vol. 57, no. 11. pp. 1443–1453, 2012.

B. Ansari and M. A. Hasan, “High-Performance Architecture of Elliptic Curve Scalar Multiplication,” Computers, IEEE Transactions on, vol. 57, no. 11. pp. 1443–1453, 2008.
http://dx.doi.org/10.1109/tc.2008.133

M. Li and A. Miri, “1 Analysis of the Hamming Weight of the Extended wmbNAF,” 2011.

A. Faz-Hernández, P. Longa, and A. Sánchez, “Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV–GLS curves (extended version),” J. Cryptogr. Eng., pp. 1–22, 2014.
http://dx.doi.org/10.1007/s13389-014-0085-7

D. Villeger and V. G. Oklobdzija, “Analysis of booth encoding efficiency in parallel multipliers using compressors for reduction of partial products,” in Signals, Systems and Computers, 1993. 1993 Conference Record of The Twenty-Seventh Asilomar Conference on, 1993, pp. 781–784.
http://dx.doi.org/10.1109/acssc.1993.342628

G. W. Reitwiesner, “Binary arithmetic,” Adv. Comput., vol. 1, pp. 231–308, 1960.
http://dx.doi.org/10.1016/s0065-2458(08)60610-5

R. Katti, “Speeding up elliptic cryptosystems using a new signed binary representation for integers,” in Digital System Design, 2002. Proceedings. Euromicro Symposium on, 2002, pp. 380–384.
http://dx.doi.org/10.1109/dsd.2002.1115395

S. Klavžar, U. Milutinović, and C. Petr, “Stern polynomials,” Adv. Appl. Math., vol. 39, no. 1, pp. 86–95, 2007.
http://dx.doi.org/10.1016/j.aam.2006.01.003

S. Md Yasin, “New Signed-Digit {0, 1, 3}-NAF Scalar Multiplication Algorithm for Elliptic Curve Over Binary Field,”.PhD Thesis,University Putra Malaysia, 2011.

H. K. Pathak and M. Shanghi, “Speeding up computation of scalar multiplication in elliptic curve cryptosystem,” Int. J. Comput. Sci. Eng., vol. 2, no. 4, pp. 1024–1028, 2010.

J. López and R. Dahab, “Fast multiplication on elliptic curves over GF (2m) without precomputation,” in Cryptographic Hardware and Embedded Systems, 1999, pp. 316–327.
http://dx.doi.org/10.1007/3-540-48059-5_27

B. Wang, H. Zhang, and Y. Wang, “An efficient elliptic curves scalar multiplication for wireless network,” in Network and Parallel Computing Workshops, 2007. NPC Workshops. IFIP International Conference on, 2007, pp. 131–134.
http://dx.doi.org/10.1109/npc.2007.43

D. Villeger and V. G. Oklobdzija, “Evaluation of Booth encoding techniques for parallel multiplier implementation,” Electron. Lett., vol. 29, no. 23, pp. 2016–2017, 1993.
http://dx.doi.org/10.1049/el:19931345

H. K. Pathak and M. Sanghi, “Speeding up Computation of Scalar Multiplication in Elliptic Curve Cryptosystem,” vol. 02, no. 04, pp. 1024–1028, 2010.

K. Wu, D. Li, H. Li, T. Chen, and F. Yu, “Partitioned Computation to Accelerate Scalar Multiplication for Elliptic Curve Cryptosystems,” in Parallel and Distributed Systems (ICPADS), 2009 15th International Conference on, 2009, pp. 551–555.
http://dx.doi.org/10.1109/icpads.2009.9

B. Wang, H. Zhang, Z. Wang, and Y. Wang, “Speeding Up Scalar Multiplication Using a New Signed Binary Representation for Integers,” in Multimedia Content Analysis and Mining SE - 35, vol. 4577, N. Sebe, Y. Liu, Y. Zhuang, and T. Huang, Eds. Springer Berlin Heidelberg, 2007, pp. 277–285.
http://dx.doi.org/10.1007/978-3-540-73417-8_35

M. Joye, “Exponentiation method resistant against side-channel and safe-error attacks.” Google Patents, 03-Jun-2014.

H. Brar and R. Kaur, “Design and implementation of block method for computing NAF,” Int. J. Comput. Appl., vol. 20, no. 1, pp. 37–41, 2011.
http://dx.doi.org/10.5120/2395-3181

Alkhatib, M., Al Salem, A., Efficient hardware implementations for tripling oriented elliptic curve crypto-system, (2014) International Review on Computers and Software (IRECOS), 9 (4), pp. 609-617.

Sharifah, M.Y., Rozi Nor Haizan, N., Jamilah, D., Zaitun, M., {0, 1, 3}-NAF representation and algorithms for lightweight elliptic curve cryptosystem in Lopez Dahab Model, (2014) International Review on Computers and Software (IRECOS), 9 (9), pp. 1541-1547.
http://dx.doi.org/10.15866/irecos.v9i9.2659

Tripathy, P.K., Biswal, D., Multiple server indirect security authentication protocol for mobile networks using elliptic curve cryptography (ECC), (2013) International Review on Computers and Software (IRECOS), 8 (7), pp. 1571-1577.

Sumathi, D., Kathik, S., Proof of retrievability using elliptic curve digital signature in cloud computing, (2014) International Review on Computers and Software (IRECOS), 9 (9), pp. 1526-1532.
http://dx.doi.org/10.15866/irecos.v9i9.2200

Aloy Anuja Mary, G., Chellappan, C., Elliptic curve cryptography (ECC) based four state quantum secret sharing (QSS) protocol, (2013) International Review on Computers and Software (IRECOS), 8 (8), pp. 1970-1979.


Refbacks

  • There are currently no refbacks.


Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize