TY - GEN

T1 - Efficient arithmetic on subfield elliptic curves over small finite fields of odd characteristic

AU - Hakuta, Keisuke

AU - Sato, Hisayoshi

AU - Takagi, Tsuyoshi

PY - 2008/4/7

Y1 - 2008/4/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=41549122016&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=41549122016&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-79104-1_22

DO - 10.1007/978-3-540-79104-1_22

M3 - Conference contribution

AN - SCOPUS:41549122016

SN - 3540791035

SN - 9783540791034

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 304

EP - 318

BT - Information Security Practice and Experience - 4th International Conference, ISPEC 2008, Proceedings

T2 - 4th Information Security Practice and Experience Conference, ISPEC 2008

Y2 - 21 April 2008 through 23 April 2008

ER -