楕円曲線暗号におけるスカラー倍算の効率化に関する検討(情報通信基礎サブソサイエティ合同研究会)

概要

論文の詳細を見る
楕円曲線暗号では楕円曲線上のスカラー倍算の効率化が重要な課題となっている.これまでに有理点P,Qに対してP+Qおよび2Pの演算を基本に加算連鎖を導く幾つかの方法が研究されている.一方で,最近,比較的小さい整数λとμに対して,λP±μQを効率的に計算する方法が,Cietらや溝添らによって発表されている.本研究では,複数の基本演算が利用できる場合に,それぞれのコストを考慮した上で,任意の整数kに対してkPを最小のコストあるいはそれに近いコストで計算する加算連鎖を求める.最小コストの加算連鎖を探索するため,加算連鎖の木を生成する複数のプログラムを開発し,それらの結果をマージして,10^5(2^<18>)程度までの最小コストのスカラー倍算kPの加算連鎖パステーブルを作成した.また,最小コストとk値との関係について考察する.さらに,パステーブルで与えられる最大の整数k_<max>に対してk_<max>≪Kとなるようなスカラー倍算KPの求め方を差分あるいは高階差分の考え方を利用して検討する.
2008-02-21