WEKO3
アイテム
Hilbert級数を用いたMQ問題の高速解法とその実装
https://ipsj.ixsq.nii.ac.jp/records/228762
https://ipsj.ixsq.nii.ac.jp/records/22876266edcb6d-63d8-4fa5-ac02-bab7903164cd
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-CSS2023149.pdf (238.6 kB)
2025年10月23日からダウンロード可能です。
|
Copyright (c) 2023 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, CSEC:会員：¥0, SPT:会員：¥0, DLIB:会員：¥0 | ||
| Item type | Symposium(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-10-23 | |||||||||
| タイトル | ||||||||||
| タイトル | Hilbert級数を用いたMQ問題の高速解法とその実装 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Efficient algorithm for solving MQ problem using Hilbert series and its implementation | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | 耐量子計算機暗号，多変数多項式暗号，MQ Challenge | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||||
| 資源タイプ | conference paper | |||||||||
| 著者所属 | ||||||||||
| 東京大学大学院情報理工学系研究科数理情報学専攻 | ||||||||||
| 著者所属 | ||||||||||
| 東京大学大学院情報理工学系研究科数理情報学専攻 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Department of Mathematical Informatics, University of Tokyo | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Department of Mathematical Informatics, University of Tokyo | ||||||||||
| 著者名 |
坂田, 康亮
× 坂田, 康亮
× 高木, 剛
|
|||||||||
| 著者名(英) |
Kosuke, Sakata
× Kosuke, Sakata
× Tsuyoshi, Takagi
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 多変数多項式暗号の安全性は，多変数多項式求解問題(MQ問題)の計算困難性を根拠としている．MQ問題を解く最も高速なアルゴリズムとしてグレブナ基底を利用したF4があるが，出力に影響のないzero reductionを多く計算する必要がある．また，次数dのグレブナ基底の生成元の個数をHilbert級数により評価し，zero reductionの回数を削減できるHilbert-drivenアルゴリズムが知られている．本論文では，ランダムに生成されたsemi-regularなMQ問題を対象とした高速アルゴリズムを提案する．Hilbert-drivenアルゴリズムは斉次イデアルの計算に制限されるが，本稿ではsemi-regularな非斉次のイデアルに対しても計算可能であることを示す．更に，非斉次なMQ問題をF4で計算する場合，Hilbert-drivenアルゴリズムのアイデアを用いてzero reductionの回数を大きく削減できることを示す．今回提案するアルゴリズムをC++で実装し，MQ問題の解読コンテストであるMQ Challengeに取り組んだ結果，新記録となる Type VI の方程式数m = 21 の問題に対して，AMD EPYC 7742 と2TB のRAM を用いて約9 時間で解読に成功したことを報告する． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | The security of multivariate polynomial cryptgraphy depends on the computational complexity of solving a multivariate quadratic polynomial system (MQ problem). One of the fastest algorithms for solving the MQ problem is F4, which computes a Grobner basis, but it requires numerous calculations of zero reduction that do not affect the output. Hilbert-driven algorithm evaluates the number of generators in the Grobner basis of degree d using Hilbert series, then it reduces the number of zero reduction computation. In this paper, we propose a high-speed algorithm designed for randomly generated semi-regular MQ problems. While the Hilbert-driven algorithm is limited to compute homogeneous ideals, we demonstrate its applicability to semi-regular non-homogeneous ideals in this work. Furthermore, when using the Hilbert-driven algorithm to solve non-homogeneous MQ problems with F4, we show the efficient achievement of reducing zero reduction for F4. We implemented the proposed algorithm in C++ and report successful decryption of a new record Type VI equations m = 21. It was achieved using an AMD EPYC 7742 processor and 2TB of RAM, and the decryption process was completed in approximately 9 hours. |
|||||||||
| 書誌情報 |
コンピュータセキュリティシンポジウム2023論文集 p. 1092-1099, 発行日 2023-10-23 |
|||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
