| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2026-07-14 15:15 次数4のMacaulay行列に対応する多項式の分類に基づくHDF4におけるzero reduction発生の十分条件 ○須藤慈英・坂田康亮・高木 剛（東大）  ISEC2026-46 SITE2026-42 BioX2026-69 HWS2026-42 ICSS2026-61 EMM2026-53 |
|
| 抄録 | （和） | 多変数多項式暗号は耐量子計算機暗号の一種であり，有限体上の多変数二次多項式系を解く MQ 問題の困難性が安全性の根拠となる．よって，その解法コストの見積もりが重要である．MQ 問題の解法に用いられるグレブナー基底計算に対し，坂田・高木は，各次数のグレブナー基底多項式数に基づいて処理する S-多項式数を制限する Hilbert Driven F4（HDF4）を提案した．しかし，この手法を次数 4 に適用すると，選択された S-多項式が 0 に簡約される現象，zero reduction が発生する場合がある．本稿では，HDF4の次数 4 におけるzero reduction 発生の十分条件を与える．この条件は，次数 4 の Macaulay 行列の張る線形部分空間を考え，HDF4が選択する次数 4 のS-多項式の集合と次数 4 のグレブナー基底の集合を比較することで，zero reductionとなるS-多項式が存在することを示すものである．実験により，十分条件は主に方程式数 m に依存することを確認し， m = 8,...,27 では 十分条件の成立とzero reduction の発生が一致した． |
| （英） | Multivariate public-key cryptography is a type of post-quantum cryptography based on the hardness of solving the MQ problem over finite fields; hence estimating the cost of solving it is important. For Gröbner basis computation for the MQ problem, Sakata and Takagi proposed Hilbert Driven F4 (HDF4), which limits processed S-polynomials in each degree using the number of Gröbner basis polynomials. However, in degree 4, a selected S-polynomial may reduce to 0, namely a zero reduction may occur. In this paper, we give a sufficient condition for zero reductions in degree 4 of HDF4. This condition shows the existence of an S-polynomial that becomes a zero reduction by considering linear subspaces spanned by the degree-4 Macaulay matrix and comparing the set of degree-4 S-polynomials selected by HDF4 with the set of degree-4 Gröbner basis elements. Experiments show that the sufficient condition mainly depends on the number m of equations, and for m=8,...,27, the satisfaction of the sufficient condition coincided with the occurrence of zero reductions. | |
| キーワード | （和） | 耐量子計算機暗号 / 多変数多項式暗号 / MQ 問題 / グレブナー基底 / HDF4 / zero reduction / / |
| （英） | post-quantum cryptography / multivariate cryptography / MQ problem / Gröbner basis / HDF4 / zero reduction / / | |
| 文献情報 | 信学技報, vol. 126, no. 107, ISEC2026-46, pp. 224-231, 2026年7月. | |
| 資料番号 | ISEC2026-46 | |
| 発行日 | 2026-07-06 (ISEC, SITE, BioX, HWS, ICSS, EMM) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2026-46 SITE2026-42 BioX2026-69 HWS2026-42 ICSS2026-61 EMM2026-53 |
|
| 研究会情報 | |
| 研究会 | 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 |
| 本文の言語 | 日本語 |
| タイトル（和） | 次数4のMacaulay行列に対応する多項式の分類に基づくHDF4におけるzero reduction発生の十分条件 |
| サブタイトル（和） | |
| タイトル（英） | A Sufficient Condition for Zero Reductions in HDF4 Based on Degree-Four Macaulay Matrix Polynomials |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 耐量子計算機暗号 / post-quantum cryptography |
| キーワード(2)（和/英） | 多変数多項式暗号 / multivariate cryptography |
| キーワード(3)（和/英） | MQ 問題 / MQ problem |
| キーワード(4)（和/英） | グレブナー基底 / Gröbner basis |
| キーワード(5)（和/英） | HDF4 / HDF4 |
| キーワード(6)（和/英） | zero reduction / zero reduction |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 須藤 慈英 / Jiei Suto / ストウ ジエイ |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： UTokyo) |
| 第2著者 氏名（和/英/ヨミ） | 坂田 康亮 / Kosuke Sakata / サカタ コウスケ |
| 第2著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： UTokyo) |
| 第3著者 氏名（和/英/ヨミ） | 高木 剛 / Tsuyoshi Takagi / タカギ ツヨシ |
| 第3著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： UTokyo) |
| 講演者 | 第1著者 |
| 発表日時 | 2026-07-14 15:15:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2026-46, SITE2026-42, BioX2026-69, HWS2026-42, ICSS2026-61, EMM2026-53 |
| 巻番号（vol） | vol.126 |
| 号番号（no） | no.107(ISEC), no.108(SITE), no.109(BioX), no.110(HWS), no.111(ICSS), no.112(EMM) |
| ページ範囲 | pp.224-231 |
| ページ数 | 8 |
| 発行日 | 2026-07-06 (ISEC, SITE, BioX, HWS, ICSS, EMM) |
[研究会発表申込システムのトップページに戻る]