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

Katja Schmidt-Samoa, Olivier Semay, Tsuyoshi Takagi

研究成果: ジャーナルへの寄稿学術誌査読

18 被引用数 (Scopus)


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.

ジャーナルIEEE Transactions on Computers
出版ステータス出版済み - 1月 2006

!!!All Science Journal Classification (ASJC) codes

  • ソフトウェア
  • 理論的コンピュータサイエンス
  • ハードウェアとアーキテクチャ
  • 計算理論と計算数学


「Analysis of fractional window recoding methods and their application to elliptic curve cryptosystems」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。