| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A New Minimal Average Weight Representation for Left-to-Right Point Multiplication Methods
November 2005 (vol. 54 no. 11)
pp. 1454-1459
This paper introduces a new radix-2 representation with the same average weight as the {\rm width}{\hbox{-}}w nonadjacent form (w{\hbox{-}}{\rm NAF}). In both w{\hbox{-}}{\rm NAF} and the proposed representations, each nonzero digit is an odd integer with absolute value less than M. However, for w{\hbox{-}}{\rm NAF}, M is of the form 2^{w-1}, while, for the proposed representation, it can be any positive integer. Therefore, using the proposed integer representation, we can use the available memory efficiently, which is attractive for devices with limited memory. Another advantage of the proposed representation over w{\hbox{-}}{\rm NAF} is that it can be obtained by scanning the bits from left-to-right. This property is also useful for memory-constrained devices because it can reduce both the time and space complexity of fast point multiplication techniques.
[1] N. Koblitz, “Elliptic Curve Cryptosysmtems,” Math. Computation, vol. 48, pp. 203-209, 1987.
[2] V. Miller, “Uses of Elliptic Curves in Cryptography,” Springer-Verlag Lecture Notes in Computer Science, vol. 218, pp. 417-426, 1987.
[3] W. Diffie and M.E. Hellman, “New Directions in Cryptography,” IEEE Trans. Information Theory, vol. 22, pp. 644-654, 1976.
[4] T. ElGamal, “A Public Key Cryptosystem and a Signature Scheme Based on the Discrete Logarithm,” IEEE Trans. Information Theory, vol. 31, pp. 469-472, 1985.
[5] I. Blake, G. Seroussy, and N. Smart, Elliptic Curves in Cryptography. Cambridge, U.K.: Cambridge Univ. Press, 1999.
[6] A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography. CRC Press, 1997.
[7] D. Gordon, “A Survey of Fast Exponentiation Methods,” J. Algorithms, vol. 27, pp. 129-146, 1998.
[8] V. Müller, “Fast Multiplication on Elliptic Curves over Small Fields of Characteristic Two,” J. Cryptology, vol. 11, pp. 219-234, 1998.
[9] J.A. Solinas, “Efficient Arithmetic on Koblitz Curves,” Designs, Codes, and Cryptography, vol. 19, pp. 195-249, 2000.
[10] B. Möller, “Improved Techniques for Fast Exponentiation,” Springer-Verlag Lecture Notes in Computer Science, vol. 2587, pp. 298-312, 2003.
[11] M. Joye and S.M. Yen, “Optimal Left-to-Right Binary Signed-Digit Recoding,” IEEE Trans. Computers, vol. 49, pp. 740-748, 2000.
[12] J.A. Muir and D.R. Stinson, “New Minimal Weight Representations for Left-to-Right Window Methods,” 2004, http://www.cacr.math.uwaterloo. catech_reports.html .
[13] K. Okeya, K. Schmidt-Samoa, C. Spahn, and T. Takagi, “Signed Binary Representations Revisited,” Springer-Verlag Lecture Notes in Computer Science, vol. 3152, pp. 123-139, 2004.
[14] J.A. Muir and D.R. Stinson, “Minimality and Other Properties of the with-$w$ Nonadjacent Form,” 2004, http://www.cacr.math.uwaterloo.catech_ reports.html .
[15] K. Hwang, Computer Arithmetic, Principles, Architecture, and Design. New York: John Wiley & Sons, 1989.
[16] R.S. Katti, “Speeding Up Elliptic Cryptosystems Using a New Signed Binary Representation for Integers,” Proc. Euro-Micro Conf. Digital Design, 2002.
[17] Ç.K. Koç, “Parallel Canonical Recoding,” Electronics Letters, vol. 32, pp. 2063-2065, 1996.
[18] H. Cohen, “Analysis of the Flexible Window Powering Algorithm,” 2004, http://www.math.u-bordeaux.fr/~cohenwindow.dvi .
[19] J.H. van Lint, Introduction to Coding Theory. Springer-Verlag, 1982.
[20] A.D. Booth, “A Signed Binary Multiplication Technique,” The Quarterly J. Mechanics and Applied Math., vol. 4, pp. 236-240, 1951.
[21] J. Guajardo and C. Paar, “Efficient Algorithms for Elliptic Curve Cryptosystems,” Springer-Verlag Lecture Notes in Computer Science, vol. 1294, pp. 342-356, 1997.
[22] Y. Sakai and K. Sakurai, “Efficient Scalar Multiplications on Elliptic Curves with Direct Computations of Several Doublings,” IEICE Trans. Fundamentals, vol. E84-A, pp. 120-129, 2001.
Index Terms:
Index Terms- Minimum-weight representation, left-to-right recoding, efficient implementation, point multiplication, elliptic curve cryptosystems.
Citation:
Majid Khabbazian, T. Aaron Gulliver, Vijay K. Bhargava, "A New Minimal Average Weight Representation for Left-to-Right Point Multiplication Methods," IEEE Transactions on Computers, vol. 54, no. 11, pp. 1454-1459, Nov. 2005, doi:10.1109/TC.2005.173
