Gröbner基底計算のためのMXL4アルゴリズムの提案

• Item type: Symposium(1)
• 公開日: 2022-10-17
• タイトル: Gröbner基底計算のためのMXL4アルゴリズムの提案
• タイトル / 言語: en
• タイトル: Proposal of Gröbener Basis Computing Algorithm MXL4
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 耐量子計算機暗号, 多変数公開鍵暗号, Groebner基底, XL法
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 中央大学研究開発機構
• 著者所属: 中央大学研究開発機構
• 著者所属(英): en
• 著者所属(英): Research and Development Initiative, Chuo University
• 著者所属(英): en
• 著者所属(英): Research and Development Initiative, Chuo University
• 著者名: 五太子, 政史; 辻井, 重男
• 著者名(英): Masahito, Gotaishi; Shigeo, Tsujii
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 多変数公開鍵暗号など，暗号解読を行うための Groebner 基底計算では汎用的な F4 等が主流だが，ペアからの S-多項式計算を行わない XL 法も改良次第で効率的な計算が期待できる．本稿では，以前提案された MXL3 の欠点を改良した MXL4 を考案し，その性能評価を行ったところ，m=2n 程度の overdetermined の連立方程式では F4 を凌ぐ計算速度が得られることが確認された．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: While Groebner Bases are computed by the generic F4, which computes them by generating S-polynomials, XL algorithms, which do not compute S-polynomials also have advantage. Here a new Groebner Bases computing algorithm, MXL4, is proposed. This algorithm was found to outperform F4 for overdetermined polynomial systems such as m=2n.
• 書誌情報: コンピュータセキュリティシンポジウム2022論文集; p. 989-995, 発行日 2022-10-17
• 出版者 / 言語: ja
• 出版者: 情報処理学会