TY - JOUR

T1 - Analysis of fractional window recoding methods and their application to elliptic curve cryptosystems

AU - Schmidt-Samoa, Katja

AU - Semay, Olivier

AU - Takagi, Tsuyoshi

PY - 2006/1

Y1 - 2006/1

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

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

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

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

U2 - 10.1109/TC.2006.3

DO - 10.1109/TC.2006.3

M3 - Article

AN - SCOPUS:33749447196

SN - 0018-9340

VL - 55

SP - 48

EP - 57

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 1

ER -