Miyaji Laboratory

Recently, most of people use some online services (shopping, social networking, etc). A cryptographic technology is absolutely imperative to prevent eavesdropping, identity fraud and so on. The cryptosystems can be roughly classified into the symmetric cryptosystem and the public key cryptosystem. In case of communication in general public, public key cryptosystem is imperative, because it has two advantages, one for being not required to share secret key, another for the ease to store the secret key. The public key cryptosystem has many schemes. RSA cryptosystem is widely used in many situations.　Elliptic Curve Cryptosystem (ECC) attracted much attention, because of two advantages, One is that the secret key size is short. Concretely speaking, ECC has been established that 224-bit ECC gives equivalent security to 2048-bit RSA. This first advantage highlights the potential increment in computing performance and savings in power/memory that can be achieved with this cryptosystem. Another advantage is that, it can construct ID-base encryption and signature and can append some function, because of the bilinear maps Elliptic Curves (EC) have.

Some research areas on ECC are construction of EC, efficient and fast approach for scalar multiplication, application, implementation on hardware, countermeasure of side-channel attack and so on. ECC have been studied in many areas from theoretical viewpoint to application viewpoint, and each area is closely concerned with others.

In this study, we emphasize a focus on efficient and fast approach for scalar multiplication. A scalar multiplication evaluates point $kP$ over EC. To compute $kP$ faster, we modified the form of EC, coordinate system and addition chain algorithm.

In some previous works, the modification of the form of EC and coordinate system includes two approaches to reduce computational complexity. One is the use of equation transformation$(2Z_1Z_2 = (Z_1+Z_2)^2-Z_1^2-Z_2^2)$. Another is the reuse of intermediate variable. Also, Meloni introduced a new type of arithmetic on elliptic curves when adding projective points sharing the same Z-coordinate (Co-Z). Co-Z operation can reduce memory use. These operations are used to calculate $kP$. The modification of addition chain algorithm has two types. The first type does not use pre-computation points. There are binary method, Non adjacent Form (NAF) and the Ciet et al proposed Ternary/Binary method. Vassil Dimitrov et al proposed addition chain algorithm using double base number system in 2005. The double base number system represents the multiplier as a sum of mixed power of 2 and 3. Another type is any algorithm using some pre-computation points. It can be classified by whether the base point $P$ of $kP$ is fixed or not. Some algorithms using some pre-computation points and unfixed $P$ are Window method, Window NAF and Fractional Window NAF. Window method and Window NAF fix the number of pre-computation points according to window size. But Fractional Window NAF is flexibly fixed with the number of pre-computation points according to odd parameter $m$. In some schemes that generate pre-computation points, Longa et al proposed a new scheme (LG09) based on $ P \rightarrow 3P \rightarrow 6P \rightarrow \cdots $ operation sequences in 2009. And LG09 proposed Conjugate Addition (ADDC) on some coordinate system. ADDC is the operation that output two points $P \pm Q$ from points $P$ and $Q$ over EC. Also, sasahara et al proposed new scheme (SMY10) based on 2-and-3 multiplication formulae (DT) in 2010. DT is operation that output two points $2P,\ 3P $ from points $P$ over EC.

We assume limited computing and memory power such as the case of mobile phones and smart cards. In previous schemes using pre-computation points without fixed $P$, these previous works evaluated computational cost, but not memory. So first ours work obtains computational cost and memory cost generating pre-computation points assuming Fractional window NAF. And we evaluate index of computational cost / unit memory, where memory is required calculating scalar multiplication $kP$. In previous schemes without using use pre-computation points, addition chain algorithm based on representation of the multiplier as a sum of powers 2 and 3 and powers 2 , 3 and 5 have been discussed but the case based on only power 3 was not discussed. We proposed an algorithm based on ternary. In particular, our algorithm is adapted for efficient Co-Z and DT ideas for such as binary and NAF.