@techreport{oai:ipsj.ixsq.nii.ac.jp:00218874, author = {林田, 大輝 and 早坂, 健一郎 and 照屋, 唯紀 and Daiki, Hayashida and Kenichiro, Hayasaka and Tadanori, Teruya}, issue = {30}, month = {Jul}, note = {ペアリング計算は関数型暗号や電子署名をはじめ,多様な高機能暗号で用いられる基本的な演算であり,Miller loop と最終べき計算の二つの演算からなる.本論文では,Miller loop で出現する疎乗算に注目し,3 次ツイストを持つ楕円曲線に適用可能な Toom-Cook 法をベースとする効率的な 3 次拡大体上の疎乗算アルゴリズムを提案する.本論文で提案する乗算アルゴリズムは,素体上の定数倍の回数を増加させる代わりに中間体上の加算回数を削減させることで計算コストの低減を図る.また,疎乗算を実行する元のどの係数が疎であっても疎乗算アルゴリズムを適用可能とする新たなテクニックを提案する.各埋め込み次数 ???? に対して,今回の疎乗算アルゴリズムが有効となる条件を評価し,特に ???? = 21, 27 の 3 次ツイストを持つ楕円曲線においては素体の乗算加算コスト比に関わらず,今回の疎乗算アルゴリズムが最も効率的であることを示す., In this paper, we propose an efficient sparse multiplication algorithm on elliptic curves with cubic twist based on the Toom-Cook method. The multiplication algorithm we propose reduces the complexity by reducing the number of addition operations on the extension field to the number of constant multiplication on the prime field.We give a new technique that enables the application of the sparse multiplication algorithm regardless of which coefficient is sparse in the Miller loop.}, title = {3次ツイストを持つペアリングフレンドリ曲線における効率的な疎乗算アルゴリズム}, year = {2022} }