You are looking at a specific version 20051214:165158 of this paper. See the latest version.

Paper 2005/454

Efficient Arithmetic on Subfield Elliptic Curves over Small Odd Characteristics

Keisuke Hakuta and Hisayoshi Sato and Tsuyoshi Takagi

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, non-adjacent form (NAF) and its generalizations (e.g., generalized non-adjacent form (GNAF) and radix-$r$ non-adjacent form ($r$NAF) \cite{CL73,TYW04}) are proposed for minimizing the non-zero densities in the representations of the scalars. On the other hand, for subfield elliptic curves, Frobenius-adic expansions of the scalars can be used for improving efficiency (\cite{Sma99+}). Unfortunately, there are only a few methods apply the techniques of NAF or its analogue to Frobenius-adic expansion, namely $\tau$-adic NAF techniques (\cite{Kob98,Sol00,BMX04} and \cite{GLS01}) for Koblitz curves and hyperelliptic Koblitz curves. In this paper, we try to combine these techniques, namely recoding methods for reducing non-zero density and Frobenius-adic expansion, and propose two new efficient recoding methods of scalars for more general family of subfield elliptic curves over odd characteristics. We also prove that the non-zero densities for the new methods are same as those for original GNAF and $r$NAF. As a result, the speed of the proposed schemes improve between 12.5{\%} and 79{\%} over that for previously known schemes.

Metadata
Available format(s)
PDF PS
Category
Implementation
Publication info
Published elsewhere. This paper has not been published anywhere.
Keywords
elliptic curve cryptosystem
Contact author(s)
k-hakuta @ sdl hitachi co jp
History
2005-12-14: received
Short URL
https://ia.cr/2005/454
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.