WEKO3
アイテム
MQ問題の計算量評価に用いる仮定の検証のためのHDF4とHDF4-simの考察
https://ipsj.ixsq.nii.ac.jp/records/240931
https://ipsj.ixsq.nii.ac.jp/records/240931e9401776-d927-4a53-a90a-848727cb0da9
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | Symposium(1) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2024-10-15 | |||||||||
タイトル | ||||||||||
タイトル | MQ問題の計算量評価に用いる仮定の検証のためのHDF4とHDF4-simの考察 | |||||||||
タイトル | ||||||||||
言語 | en | |||||||||
タイトル | Considerations on HDF4 and HDF4-sim for Assumptions in the Computational Complexity Evaluation of MQ Problems | |||||||||
言語 | ||||||||||
言語 | jpn | |||||||||
キーワード | ||||||||||
主題Scheme | Other | |||||||||
主題 | 耐量子計算機暗号,多変数多項式暗号,MQ 問題,Gr¨obner 基底 | |||||||||
資源タイプ | ||||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||||
資源タイプ | conference paper | |||||||||
著者所属 | ||||||||||
東京大学 | ||||||||||
著者所属 | ||||||||||
東京大学 | ||||||||||
著者所属(英) | ||||||||||
en | ||||||||||
The University of Tokyo | ||||||||||
著者所属(英) | ||||||||||
en | ||||||||||
The University of Tokyo | ||||||||||
著者名 |
坂田, 康亮
× 坂田, 康亮
× 高木, 剛
|
|||||||||
著者名(英) |
Kosuke, Sakata
× Kosuke, Sakata
× Tsuyoshi, Takagi
|
|||||||||
論文抄録 | ||||||||||
内容記述タイプ | Other | |||||||||
内容記述 | 現在,米国政府機関NISTにより,次世代の耐量子計算機暗号の選定が進められている.多変数多項式暗号は候補の暗号方式であり,その安全性は多変数連立二次代数方程式の求解(MQ問題)の計算困難性に基づいている.MQ問題の解法には,F4にHilbert-drivenの方法を適用した高速なアルゴリズムが提案されており,その計算量評価はアルゴリズム中に生成される行列の大きさを計算し,掛け算の回数を算出するである.また,計算量算出にはアルゴリズムの前半部分であるHDF4と後半部分のM1の計算量が等しいという仮定を置いている.本発表では,仮定の検証をおこなうために,HDF4の効率化と,その方法のHDF4-simへの適用方法を提案する.HDF4の行列演算の効率化を目的とし,計算するS多項式の集合の分割と簡約に使用する多項式の分割方法を提案し,行列の密度を上昇させる方法を示す.また,行列の分割に対応したHDF4-simを構築し,効率化されたHDF4の計算量評価が可能である.最後に,上昇過程と下降過程の計算量を比較することで,仮定が十分に大規模なMQ問題で正しいことを示唆する結果が得られた. | |||||||||
論文抄録(英) | ||||||||||
内容記述タイプ | Other | |||||||||
内容記述 | The U.S. government agency NIST is currently selecting next-generation post-quantum cryptographic schemes. Among the candidates is multivariate polynomial cryptography, whose security is based on the computational difficulty of solving multivariate quadratic (MQ) equations. A fast algorithm has been proposed to solve the MQ problem, utilizing a Hilbert-driven approach to the F4 algorithm. This algorithm's complexity is evaluated by estimating the size of the matrices generated and counting the number of multiplications. It assumes that the computational complexity of the HDF4 is equal to that of the M1. This presentation proposes optimizing HDF4 and applying this optimization to HDF4-sim to test the assumption. The goal is to improve the efficiency of matrix operations in HDF4 by partitioning the set of S-polynomials and dividing the polynomials used for reduction, thus increasing matrix density. HDF4-sim corresponding to this partitioning is also constructed, enabling a more accurate evaluation of the optimized HDF4's complexity. Finally, by comparing the complexities of the ascending and descending phases, we suggest that the assumption holds for sufficiently large MQ problems. |
|||||||||
書誌情報 |
コンピュータセキュリティシンポジウム2024論文集 p. 1385-1392, 発行日 2024-10-15 |
|||||||||
出版者 | ||||||||||
言語 | ja | |||||||||
出版者 | 情報処理学会 |