| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2026-07-15 09:15 格子暗号におけるIncomplete NTTとToom-4を用いたハイブリッド多項式乗算の計算量解析 ○奥 さくら・工藤桃成（福岡工大）  ISEC2026-57 SITE2026-53 BioX2026-80 HWS2026-53 ICSS2026-72 EMM2026-64 |
|
| 抄録 | （和） | 現在普及しているRSA暗号や楕円曲線暗号などの安全性は，素因数分解問題や離散対数問題の計算困難性に基づいている． しかし，これらは量子コンピュータが実現すると，Shorのアルゴリズムにより現実的な時間で解読可能となる危険性がある． そのため，量子計算機による解読にも耐えうる暗号である耐量子計算機暗号が注目されており，ML-KEMやML-DSAをはじめとした格子暗号の標準化が既に行われている． ML-KEMやML-DSAといった剰余環ベースの格子暗号では，有限体上の一変数多項式環の剰余環を用いており，その剰余環上の乗算の効率が暗号方式全体の効率に大きく影響する． このような乗算の高速化手法として数論変換(Number Theoretic Transform; NTT)が広く用いられているが，選択可能なモジュラスに制約がある．本研究では，その制約を緩和するIncomplete NTTに着目し，Toom-4およびKaratsuba法を組み込んだ場合の計算量を解析する． 特に，Toom-4に対して有限体上の加減算回数と乗算回数を分離した定数因子込みの演算回数評価を与え，Incomplete NTTの計算量モデルへ組み込む． さらに，得られた計算量モデルを用いて，Toom-4，Karatsuba法，および両者のハイブリッドを統一的に評価し，最適な再帰深さを決定する． また，ML-KEMおよびML-DSAの推奨モジュラスと同程度のサイズを持つNTT-unfriendlyな素数に対してPython実装による実験を行う． その結果，利用可能なNTT深さが制限される場合には，Toom-4とKaratsuba法のハイブリッドが有効であることを示す． |
| （英） | The security of public-key cryptosystems such as RSA and elliptic curve cryptography is based on the computational hardness of integer factorization and the discrete logarithm problem. However, once large-scale quantum computers become available, these cryptosystems may be broken in practical time by Shor's quantum algorithm. Consequently, post-quantum cryptography, which is designed to remain secure against quantum attacks, has attracted significant attention. In particular, lattice-based cryptosystems such as ML-KEM and ML-DSA have already been standardized. These cryptosystems are built on quotient rings of univariate polynomial rings over finite fields, and the efficiency of polynomial multiplication in such rings has a significant impact on the overall performance of the cryptosystem. The Number Theoretic Transform (NTT) is widely used for accelerating polynomial multiplication in this setting, but it imposes restrictions on the choice of modulus. In this work, we focus on the Incomplete NTT technique, which relaxes these restrictions, and provide a rigorous complexity analysis of hybrid multiplication methods combining Incomplete NTT with Karatsuba and Toom-4 multiplication. In particular, we derive explicit operation counts for Toom-4, separating additions/subtractions and multiplications over finite fields, including constant factors. We further evaluate the resulting complexity model for NTT-unfriendly moduli of sizes comparable to the recommended moduli of ML-KEM and ML-DSA, and present experimental results obtained from Python implementations. Our results show that a Toom-4/Karatsuba hybrid becomes effective when the available NTT depth is limited. |
|
| キーワード | （和） | 多項式乗算 / Incomplete NTT / Toom-Cook法 / Karatsuba法 / 格子暗号 / 計算量解析 / ハイブリッド算法 / |
| （英） | Polynomial multiplication / Incomplete NTT / Toom-Cook / Karatsuba / lattice-based cryptography / complexity analysis / hybrid algorithms / | |
| 文献情報 | 信学技報, vol. 126, no. 107, ISEC2026-57, pp. 306-313, 2026年7月. | |
| 資料番号 | ISEC2026-57 | |
| 発行日 | 2026-07-06 (ISEC, SITE, BioX, HWS, ICSS, EMM) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2026-57 SITE2026-53 BioX2026-80 HWS2026-53 ICSS2026-72 EMM2026-64 |
|
| 研究会情報 | |
| 研究会 | BioX HWS ISEC SITE ICSS EMM IPSJ-CSEC IPSJ-SPT |
| 開催期間 | 2026-07-13 - 2026-07-15 |
| 開催地（和） | 札幌コンベンションセンター |
| 開催地（英） | Sapporo Convention Center |
| テーマ（和） | セキュリティ、一般 （セキュリティサマーサミット2026） |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2026-07-BioX-HWS-ISEC-SITE-ICSS-EMM-CSEC-SPT-SEC |
| 本文の言語 | 日本語 |
| タイトル（和） | 格子暗号におけるIncomplete NTTとToom-4を用いたハイブリッド多項式乗算の計算量解析 |
| サブタイトル（和） | |
| タイトル（英） | Complexity Analysis of Hybrid Polynomial Multiplication Based on Incomplete NTT and Toom-4 for Lattice-Based Cryptography |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 多項式乗算 / Polynomial multiplication |
| キーワード(2)（和/英） | Incomplete NTT / Incomplete NTT |
| キーワード(3)（和/英） | Toom-Cook法 / Toom-Cook |
| キーワード(4)（和/英） | Karatsuba法 / Karatsuba |
| キーワード(5)（和/英） | 格子暗号 / lattice-based cryptography |
| キーワード(6)（和/英） | 計算量解析 / complexity analysis |
| キーワード(7)（和/英） | ハイブリッド算法 / hybrid algorithms |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 奥 さくら / Sakura Oku / オク サクラ |
| 第1著者 所属（和/英） | 福岡工業大学 (略称： 福岡工大) Fukuoka Institute of Technology (略称： Fukuoka Inst. of Tech.) |
| 第2著者 氏名（和/英/ヨミ） | 工藤 桃成 / Momonari Kudo / クドウ モモナリ |
| 第2著者 所属（和/英） | 福岡工業大学 (略称： 福岡工大) Fukuoka Institute of Technology (略称： Fukuoka Inst. of Tech.) |
| 講演者 | 第1著者 |
| 発表日時 | 2026-07-15 09:15:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2026-57, SITE2026-53, BioX2026-80, HWS2026-53, ICSS2026-72, EMM2026-64 |
| 巻番号（vol） | vol.126 |
| 号番号（no） | no.107(ISEC), no.108(SITE), no.109(BioX), no.110(HWS), no.111(ICSS), no.112(EMM) |
| ページ範囲 | pp.306-313 |
| ページ数 | 8 |
| 発行日 | 2026-07-06 (ISEC, SITE, BioX, HWS, ICSS, EMM) |
[研究会発表申込システムのトップページに戻る]