WEKO3
アイテム
UOV署名方式の変種に対するCSS2023で提案したグレブナー基底計算アルゴリズムによる計算量評価
https://ipsj.ixsq.nii.ac.jp/records/240932
https://ipsj.ixsq.nii.ac.jp/records/24093268455571-c4b2-48a3-877d-a136e76ac336
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-CSS2024186.pdf (348.7 kB)
2026年10月15日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, CSEC:会員：¥0, SPT:会員：¥0, DLIB:会員：¥0 | ||
| Item type | Symposium(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-10-15 | |||||||||
| タイトル | ||||||||||
| 言語 | ja | |||||||||
| タイトル | UOV署名方式の変種に対するCSS2023で提案したグレブナー基底計算アルゴリズムによる計算量評価 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | The complexity estimation on variants of UOV signature scheme using the Groebner basis algorithm proposed in CSS2023 | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | グレブナー基底, 耐量子計算機暗号, 多変数多項式暗号, UOV | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||||
| 資源タイプ | conference paper | |||||||||
| 著者所属 | ||||||||||
| 東京大学 | ||||||||||
| 著者所属 | ||||||||||
| 九州大学 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| The University of Tokyo | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Kyushu University | ||||||||||
| 著者名 |
坂田, 康亮
× 坂田, 康亮
× 池松, 泰彦
|
|||||||||
| 著者名(英) |
Kosuke, Sakata
× Kosuke, Sakata
× Yasuhiko, Ikematsu
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | UOVは有限体上の連立二次方程式の求解問題(MQ問題)の計算困難性を利用した署名方式であり，米国政府機関NISTが現在行なっている耐量子計算機暗号(PQC)の署名方式追加公募において注目を集めている．MQ問題はNP困難であることが示されており，その求解手法についてはグレブナー基底計算アルゴリズムを中心に現在でも様々な研究が行われている．その一つとしてCSS2023で坂田らによって提案されたアルゴリズムがあり，これはMQ問題の解読コンテストであるFukuoka MQ challengeにおいて世界記録を達成している．この論文では，UOVまたはNISTの追加公募に投稿されたUOVの変種に対して，坂田らのアルゴリズムを用いた攻撃計算量評価について考察する． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | UOV is a signature scheme based on the hardness of the problem finding a solution of quadratic equations over a finite field (called MQ problem), and is attracting attention in the additional competition of NIST PQC standardization project. The MQ problem is shown to be NP hard, and there are various studies to solve it, focusing on Groebner basis algorithm. Recently, Sakata et al. proposed a new Groebner basis algorithm in CSS2023, and achieved a world record in Fukuoka MQ challenge. In this paper, we observe the complexity estimation of some attacks for UOV and its variants using the algorithm of Sakata et al. |
|||||||||
| 書誌情報 |
コンピュータセキュリティシンポジウム2024論文集 p. 1393-1400, 発行日 2024-10-15 |
|||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
