2冪算における直接計算法を用いたマルチスカラー倍算の効率性評価

概要

論文の詳細を見る
楕円曲線に基づくデジタル署名アルゴリズム(ECDSA)を使った署名検証において最も時間を要する演算は,2つのスカラーを用いるマルチスカラー倍算である.マルチスカラー倍算において,予備計算を必要とせずに高速に計算するクラスとして,Interleave法とNAF (IL-NAF),Interleave法とMOF (IL-MOF)が知られている.IL-NAF/MOFを用いたマルチスカラー倍算では,連続する零桁(ゼロラン)の長さによってマルチスカラー倍算の効率性が評価できるため,IL-NAF/MOFのゼロランの長さ(ゼロラン長)の解析は重要である.本稿では,Markov鎖を用いた桁の分布解析からゼロランの平均長と発生確率を理論的に解析した.IL-NAFの平均ゼロラン長は3,IL-MOFの平均ゼロラン長は256/85となる.また,ゼロランの分布確率の解析をマルチスカラー倍算の計算量の見積りに適用し,2^kP直接計算法を用いた計算方式が2倍算を繰り返し計算する方式よりも4.7〜4.8%高速になることを証明した.
2007-12-12