Analysis of Fractional Window Recoding Methods and Their Application to Elliptic Curve Cryptosystems
|
Elliptic curve cryptosystems (ECC) are suitable for memory-constraint devices like smart cards due to their small key-size. A standard way of computing elliptic curve scalar multiplication, the most frequent operation in ECC, is window methods, which enhance the efficiency of the binary method at the expense of some precomputation. The most established window methods are sliding window on NAF (NAF+SW), wNAF, and wMOF, where NAF and MOF are acronyms for nonadjacent form and mutually opposite form, respectively. A common drawback of these schemes is that only a small portion of the numbers are possible sizes for precomputation tables. Therefore, in practice, it is often necessary to waste memory because there is no table fitting exactly the available storage. In the case of wNAF, there exists a variant that allows arbitrary table sizes, the so-called fractional wNAF (Frac--wNAF). In this paper, we give a comprehensive proof using Markov theory for the estimation of the average nonzero density of the Frac-wNAF representation. Then, we propose the fractional wMOF (Frac-wMOF), which is a left-to-right analogue of Frac-wNAF. We prove that Frac-wMOF inherits the outstanding properties of Frac-wNAF. However, because of its left-to-right nature, Frac-wMOF is preferable as it reduces the memory consumption of the scalar multiplication. Finally, we show that the properties of all discussed previous schemes can be achieved as special instances of the Frac-wMOF method. To demonstrate the practicability of Frac-wMOF, we develop an on-the-fly algorithm for computing elliptic curve scalar multiplication with a flexibly chosen amount of memory.
[1] 48 R.M. Avanzi, “On Multi-Exponentiation in Cryptography,” For the Advanced Research on Ellipitic and Hyperelliptic Curve Cryptography Project, Oct. 2002, http://www.arehcc.com/downloadexporev.pdf .
[2] R.M. Avanzi, “A Note on the Signed Sliding Window Integer Recoding and a Left-to-Right Analogue,” Selected Areas in Cryptography, H. Handschuh and M.A. Hasan, eds., pp. 130-143, Springer, 2004.
[3] I.F. Blake, G. Seroussi, and N.P. Smart, Elliptic Curves in Cryptography. Cambridge Univ. Press, 1999.
[4] H. Cohen, A. Miyaji, and T. Ono, “Efficient Elliptic Curve Exponentiation Using Mixed Coordinates,” Proc. ASIACRYPT, K. Ohta and D. Pei, eds., pp. 51-65, Springer, 1998.
[5] D.M. Gordon, “A Survey of Fast Exponentiation Methods,” J. Algorithms, vol. 27, pp. 129-146, 1998.
[6] O. Häggström, Finite Markov Chains and Algorithmic Applications. Cambridge Univ. Press, 2002.
[7] C. Heuberger, R. Katti, H. Prodinger, and X. Ruan, “The Alternating Greedy Expansion and Applications to Left-to-Right Algorithms in Cryptography,” Theoretical Computer Science A, to appear, http://www.opt.math.tu-graz.ac.at/~cheub publica tions/.
[8] IEEE P1363-2000, “Standard Specifications for Public-Key Cryptography,” http://grouper.ieee.org/groups1363/, 2000.
[9] J. Jedwab and C.J. Mitchell, “Minimum Weight Modified Signed-Digit Representations and Fast Exponentiation,” Electronics Letters, vol. 25, pp. 1171-1172, 1989.
[10] M. Joye and S.-M. Yen, “Optimal Left-to-Right Binary Signed-Digit Recoding,” IEEE Trans. Computers, vol. 49, no. 7, pp. 740-748, July 2000.
[11] D.E. Knuth, The Art of Computer Programmming, Vol. 2: Seminumerical Algorithms, second ed. Reading, Mass.: Addison-Wesley, 1981.
[12] A.J. Menezes, P.C. van Oorschot, and S.A. Vanston, Handbook of Applied Cryptography. CRC Press, 1996, http://www.cacr.math. uwaterloo.cahac/.
[13] B. Möller, “Improved Techniques for Fast Exponentiation,” Proc. Int'l Conf. Information Security and Cryptology (ICISC), P.J. Lee and C.H. Lim, eds., pp. 298-312, 2002.
[14] B. Möller, “Fractional Windows Revisited: Improved Signed-Digit Representations for Efficient Exponentiation,” Proc. Int'l Conf. Information Security and Cryptology (ICISC), C. Park and S. Chee, eds., pp. 137-153, 2004.
[15] F. Morain and J. Olivos, “Speeding up the Computations on an Elliptic Curve Using Addition-Subtraction Chains,” RAIRO Theoretical Informatics and Applications, vol. 24, pp. 531-543, 1990.
[16] J.A. Muir and D.R. Stinson, “New Minimal Weight Representations for Left-to-Right Window Methods,” Proc. Cryptographers Track-RSA Conf. (CT-RSA), A.J. Menezes, ed., pp. 366-383, 2005.
[17] K. Okeya, K. Schmidt-Samoa, C. Spahn, and T. Takagi, “Signed Binary Representations Revisited,” Proc. CRYPTO, M.K. Franklin, ed., pp. 123-139, 2004.
[18] K. Okeya, K. Schmidt-Samoa, C. Spahn, and T. Takagi, “Signed Binary Representations Revisited,” Cryptology ePrint Archive: Report 2004/195, 2004.
[19] G.W. Reitwiesner, “Binary Arithmetic,” Advances in Computers, vol. 1, pp. 231-308, Academic Press, 1960.
[20] K. Schmidt-Samoa, O. Semay, and T. Takagi, “Analysis of Some Efficient Window Methods and Their Application to Elliptic Curve Cryptosystems,” technical report, Technische Universität Darmstadt, Aug. 2004, http://www.informatik.tu-darmstadt. de/TI/ Veroeffentlichung/reportsREAD%ME.TR.html#2004 .
[21] J.A. Solinas, “Efficient Arithmetic on Koblitz Curves,” Designs, Codes, and Cryptography, vol. 19, pp. 195-249, 2000.
[22] E. De Win, S. Mister, B. Preneel, and M.J. Wiener, “On the Performance of Signature Schemes Based on Elliptic Curves,” Proc. Int'l Symp. Algorithmic Number Theory (ANTS), J. Buhler, ed., pp. 252-266, Springer, 1998.
Index Terms:
Index Terms- Public key cryptosystems, algorithm design and analysis, elliptic curve scalar multiplication, signed binary representations.
Citation:
Katja Schmidt-Samoa, Olivier Semay, Tsuyoshi Takagi, "Analysis of Fractional Window Recoding Methods and Their Application to Elliptic Curve Cryptosystems," IEEE Transactions on Computers, vol. 55, no. 1, pp. 48-57, Jan. 2006, doi:10.1109/TC.2006.3
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb