η_Tペアリングの最終べきについて

摘要

近年暗号で用いられるペアリングにTateペアリングとη_Tペアリングがある.これらの計算は共に,(1)(出力が剰余群の元である)アルゴリズムの計算,(2)最終べきの計算,とを行う.(1)による値は数学的には意味を持つが,暗号にペアリングを用いるときは,(2)の最終べきの計算も必要となる.(1)に対応するTateペアリングのアルゴリズムにはMillerのアルゴリズムやDuursma-Leeアルゴリズムがあり,η_Tペアリングのアルゴリズムのループの回数はDuursma-Leeアルゴリズムの約半分となる.これまでの研究により(1)の部分に計算は大幅に高速化されてきた7.Duursma-Leeアルゴリズムには最終べきを効率的に計算する方法がある8,9が,η_Tペアリングの最終べきに関しては研究されていない.最終べきも場合によっては,(1)の部分に約半分の計算量を占めるため,効率化が必要である.σ^2=-1となるσに対して{1,σ}を基底として2次拡大体を構成すると,その乗法群の部分群であるトーラスT_2では逆元が容易に得られるという特性を持つ.本稿はこの特性を使って標数3の体上のη_Tペアリングの効率的な最終べきの計算法を提案する.提案する最終べきの計算法ではTateペアリングの最終べきの計算量に比べて,36回のIF_3^nでの乗算と3(n+1)回の3乗算と何回かの加減算が増加するのみである.提案手法によりη_Tペアリングは15の高速化が達成される.更にGrangerらの手法13のη_Tペアリングへの適用法とη_TペアリングからTateペアリングへの効率的な変換方法も提案する.