メモリを考慮した事前計算点生成手法の提案

摘要

楕円曲線暗号は次世代の公開鍵暗号として注目されている．楕円曲線暗号の効率性を決定付ける演算はスカラー倍算と呼ばれ，高速化や使用するメモリ量の削減など多く研究されている．我々は既存研究の中で連続2倍算公式，Conjugate Additionと2-and-3倍算公式に着目した．本論文では2-and-3倍算公式の改良と混合ダブル2倍算公式を提案し，事前計算点生成手法の改良を行った．事前計算に必要とする計算量とメモリ量を求め，既存手法と比較を行った．そして，Fractional window NAF法へ適用し，スカラー倍算全体の計算量とメモリ量の評価を行った．結果，事前計算点生成手法では事前計算点数5つ（m＝11）の場合，既存手法より2変数分のメモリ量を削減できた．また，事前計算点を4つ以上保持する場合，I/M比が5.6より大きい実装環境において提案手法が高速となった．また，Fractional window NAFを利用してI/M比が14.15より大きい実装環境において16メモリ量で計算できる．I/M比が7≦I/M≦14.15の実装環境において22メモリ量で計算できる．