Efficient Arithmetic on Subfield Elliptic Curves over Small Finite Fields of Odd Characteristic
In elliptic curve cryptosystems, scalar multiplications performed on the curves have much effect on the efficiency of the schemes, and many efficient methods have been proposed. In particular, recoding methods of the scalars play an important role in the
- PDF / 316,115 Bytes
- 15 Pages / 430 x 660 pts Page_size
- 46 Downloads / 210 Views
Hitachi, Ltd., Systems Development Laboratory, 1099, Ohzenji, Asao-ku, Kawasaki, 215-0013, Japan {keisuke.hakuta.cw, hisayoshi.sato.th}@hitachi.com 2 Future University - Hakodate, School of Systems Information Science, 116-2, Kamedanakano-cho, Hakodate, 041-8655, Japan [email protected]
Abstract. In elliptic curve cryptosystems, scalar multiplications performed on the curves have much effect on the efficiency of the schemes, and many efficient methods have been proposed. In particular, recoding methods of the scalars play an important role in the performance of the algorithm used. For integer radices, the non-adjacent form (NAF) [21] and its generalizations (e.g., the generalized non-adjacent form (GNAF) [6] and the radix-r non-adjacent form (rNAF) [28]) have been proposed for minimizing the non-zero densities in the representations of the scalars. On the other hand, for subfield elliptic curves, the Frobenius expansions of the scalars can be used for improving efficiency [25]. Unfortunately, there are only a few methods apply the techniques of NAF or its analogue to the Frobenius expansion, namely τ -adic NAF techniques on Koblitz curves [16,27,3] and hyperelliptic Koblitz curves [10]. In this paper, we try to combine these techniques, namely recoding methods for reducing non-zero density and the Frobenius expansion, and propose two new efficient recoding methods of scalars on more general family of subfield elliptic curves in odd characteristic. We also prove that the non-zero densities for the new methods are same as those for the original GNAF and rNAF. As a result, the speed of the proposed methods improve between 8% and 50% over that for the Frobenius expansion method. Keywords: Elliptic Curves, Non-Adjacent Form (NAF), Frobenius Expansions, τ -adic NAF (τ -NAF), φ-adic NAF (φ-NAF).
1 Introduction Elliptic curve cryptosystems (ECC) were proposed in 1985 independently by Victor Miller [19] and by Neal Koblitz [14]. Since ECC provide many advantages, for example, shorter key length and faster computation speed than those of RSA cryptosystems, ECC have been the focus of much attention. In ECC, each protocol such as ECDH, EC-ElGamal, and ECDSA involves scalar multiplications for given points on an elliptic curve by positive integers. These multiplications have much effect on the efficiency of the schemes, and many efficient methods have been proposed. L. Chen, Y. Mu, and W. Susilo (Eds.): ISPEC 2008, LNCS 4991, pp. 304–318, 2008. c Springer-Verlag Berlin Heidelberg 2008
Efficient Arithmetic on Subfield Elliptic Curves
305
As one such method, the use of subfield elliptic curves (i.e. elliptic curves over finite fields which are actually defined over some subfield [4]) is especially attractive because by using the Frobenius maps, which is efficiently computed, scalar multiplication on subfield elliptic curves can be performed much faster than that on curves over prime fields. Koblitz [15] suggested anomalous binary curves, and M¨uller [18] extended Koblitz’s idea to achieve the Frobenius expansions over smal
Data Loading...
