パステーブルを用いた楕円スカラー倍算における高階差分演算に関する考察

概要

論文の詳細を見る
楕円曲線暗号における主な処理は,楕円曲線上の有理点Pのスカラー倍点kPの計算であるため,スカラー倍点の効率的な計算法の開発が重要な課題となっている.本研究では,あらかじめ作成されたパステーブルに従って,スカラー倍点kPを小さい計算量(コスト)で求める方法(これをパステーブル法と呼ぶ)について検討する.パステーブル法では,ROMなどで構成されるパステーブルに,各整数kに対してkPを最小コストで計算するパスが記憶されている.このパスはあらかじめ探索されたものであり,P+Q,2Pだけでなく,比較的小さい整数λとμに対するλP±μQがパスを構成する基本演算として使われている.この論文では,パステーブルで与えられる最大の整数k_<max>に対して,k_<max>≪Kとなるようなスカラー倍点KPを求めるアルゴリズムの一つとして,高階差分の考え方を利用する方法を提案する.高階差分を用いた場合の計算量を評価し,差分を用いない場合や,通常のバイナリ法などの演算コストと比較する.
2008-05-09