楕円曲線上の点のスカラー倍点計算は、公開鍵暗号の一種である楕円曲線暗号方式(Elliptic Curve Cryptosystems, ECC)において鍵生成や暗号化・復号化処理の中核を成す重要な処理である。具体的には楕円曲線上の点 M と非負整数 e を入力とし、M を e 個「足し合わせた」点
eM = M + M + … + M
を求める計算である。ここで演算記号 '+' は、楕円曲線上に導入される点と点の加法を表す。楕円曲線暗号方式の特徴の1つに、従来の代表的なRSA暗号方式やElGamal暗号方式と同等の安全性をより短い長さの鍵で実現可能であることが挙げられる(一般に、1024bitのRSA暗号方式が160bitのECC, 2048bitのRSA暗号方式が211bitのECCに相当するといわれる)。この特徴を生かしてICカードによる認証及び小型携帯端末等、演算能力の制限された機器への実装が進んでいる。
しかし近年の計算機の演算能力の向上は著しく、現在の鍵の長さで安全であるとは保証できなくなってきており、将来的な鍵の長さの増大は避けられないと考えられている。これは暗号の各種処理時間の増大を意味する。特に、演算能力の制限された機器への実装を考えた場合、暗号の各種処理の更なる効率化は必須である。
本研究では楕円曲線上の点のスカラー倍点計算を効率化するアルゴリズムを提案し、現在楕円曲線暗号方式で使用されている160bit, 及びそれ以上のサイズの有限体の下で実行速度の向上、演算回数の削減の効果が得られることを示した。