暗号の安全性解析に向けたグレブナー基底の計算量理論の定式化

• Item type: Symposium(1)
• 公開日: 2024-10-15
• タイトル: 暗号の安全性解析に向けたグレブナー基底の計算量理論の定式化
• タイトル / 言語: en
• タイトル: Formulation of the complexity theory on Groebner basis computation with the view toward to cryptanalysis
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 福岡工業大学情報工学部
• 著者所属: 立教大学理学部
• 著者所属(英): en
• 著者所属(英): Fukuoka Institute of Technology
• 著者所属(英): en
• 著者所属(英): Rikkyo University
• 著者名: 工藤, 桃成; 横山, 和弘
• 著者名(英): Momonari, Kudo; Kazuhiro, Yokoyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 多変数多項式系を解くための主要な方法にグレブナー基底計算があり，多変数多項式暗号をはじめとした公開鍵暗号に対する攻撃としても利用される．しかし，グレブナー基底の計算量評価は理論的に非常に難しい問題であるため，暗号分野の先行研究においては数学的な正確さを欠く（あるいは誤った）議論がなされていることも少なくない．本稿では，そのような議論がなされてきた事例として半正則性と求解次数に着目し，数学的に正確かつ厳密な定式化を行う．その上で，半正則な非斉次多項式列に対する求解次数の上界を評価し，グレブナー基底の計算量評価式を正しい形で与える．さらに，従来の半正則性の定義を拡張することで，よりタイトな計算量評価式が得られたので，これについても紹介し，暗号の安全性解析への応用可能性を議論する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Groebner basis computation is a typical tool for solving multivariate polynomial systems, and it is applied to constructing effective attacks against public key cryptosystems. However, it is theoretically quite difficult to estimate the complexity of Groebner basis computation, which has caused mathematically inaccurate (or incorrect) discussions in the cryptographic literature. In this paper, we focus on semi-regularity and solving degree, and formulate them in a mathematically accurate and precise way. Then we estimate an upper bound on solving degree for semi-regular inhomogeneous polynomial sequences, and present formulae to measure the complexity of the Groebner basis computation for such a sequence. Furthermore, we obtain a tighter bound on the complexity by extending the notion of semi-regular, and finally discuss applications of our theoretical results to analyzing cryptanalysis.
• 書誌情報: コンピュータセキュリティシンポジウム2024論文集; p. 861-868, 発行日 2024-10-15
• 出版者 / 言語: ja
• 出版者: 情報処理学会