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

• Item type: SIG Technical Reports(1)
• 公開日: 2022-07-12
• タイトル: 3次ツイストを持つペアリングフレンドリ曲線における効率的な疎乗算アルゴリズム
• タイトル / 言語: en
• タイトル: An Efficient Sparse Multiplication Algorithm for Pairing-Friendly Elliptic Curves With Cubic Twist
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: ICSS
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 三菱電機株式会社情報技術総合研究所
• 著者所属: 三菱電機株式会社情報技術総合研究所
• 著者所属: 産業技術総合研究所
• 著者所属(英): en
• 著者所属(英): Mitsubishi Electric Corporation Information Technology R&D Center
• 著者所属(英): en
• 著者所属(英): Mitsubishi Electric Corporation Information Technology R&D Center
• 著者所属(英): en
• 著者所属(英): National Institute of Advanced Industrial Science and Technology
• 著者名: 林田, 大輝; 早坂, 健一郎; 照屋, 唯紀
• 著者名(英): Daiki, Hayashida; Kenichiro, Hayasaka; Tadanori, Teruya
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ペアリング計算は関数型暗号や電子署名をはじめ，多様な高機能暗号で用いられる基本的な演算であり，Miller loop と最終べき計算の二つの演算からなる．本論文では，Miller loop で出現する疎乗算に注目し，3 次ツイストを持つ楕円曲線に適用可能な Toom-Cook 法をベースとする効率的な 3 次拡大体上の疎乗算アルゴリズムを提案する．本論文で提案する乗算アルゴリズムは，素体上の定数倍の回数を増加させる代わりに中間体上の加算回数を削減させることで計算コストの低減を図る．また，疎乗算を実行する元のどの係数が疎であっても疎乗算アルゴリズムを適用可能とする新たなテクニックを提案する．各埋め込み次数 ???? に対して，今回の疎乗算アルゴリズムが有効となる条件を評価し，特に ???? = 21, 27 の 3 次ツイストを持つ楕円曲線においては素体の乗算加算コスト比に関わらず，今回の疎乗算アルゴリズムが最も効率的であることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12628305
• 書誌情報: 研究報告セキュリティ心理学とトラスト（SPT）; 巻 2022-SPT-48, 号 30, p. 1-8, 発行日 2022-07-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8671
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会