3次ツイストを持つペアリングフレンドリ曲線における効率的な疎乗算アルゴリズム

摘要

ペアリング計算は関数型暗号や電子署名をはじめ，多様な高機能暗号で用いられる基本的な演算であり，Miller loopと最終べき計算の二つの演算からなる．本論文では，Miller loopで出現する疎乗算に注目し，3次ツイストを持つ楕円曲線に適用可能なToom-Cook法をベースとする効率的な3次拡大体上の疎乗算アルゴリズムを提案する．本論文で提案する乗算アルゴリズムは，素体上の定数倍の回数を増加させる代わりに中間体上の加算回数を削減させることで計算コストの低減を図る．また，疎乗算を実行する元のどの係数が疎であっても疎乗算アルゴリズムを適用可能とする新たなテクニックを提案する．各埋め込み次数kに対して，今回の疎乗算アルゴリズムが有効となる条件を評価し，特にk＝21, 27の3次ツイストを持つ楕円曲線においては素体の乗算加算コスト比に関わらず，今回の疎乗算アルゴリズムが最も効率的であることを示す．