グレブナー基底計算の最適化に関する一考察: 時号解析のためのグレブナー基底計算

摘要

The most basic way to cryptanalyze Multivariate Public Key Cryptosystems (MPKC) is solving the equation system generated by the public key and the ciphertext. Most commonly used way to solve the equation system is computing the Grobner Bases. Usually F_4, commonly used Grobner Bases algorithm is used. But since F_4 is designed for general polynomial sets, Mutant Grobner Bases (MGB) algorithm is more suitable for MPKC. It is more appropriate using MGB in evaluating the security of MPKC.%多変数公開鍵暗号の安全性を評価するためには，公開鍵と暗号文による連立方程式を解く攻撃が最も汎用的である．このために使われる手法はグレブナ一基底計算であり，通常は為アルゴリズムが使われている．理由は，数式処理システムに実装されているアルゴリズムの中では為が最も高速であるためである．しかし，最近提案されたMutant Groebner Bases（MGB）アルゴリズムはMPKC公開鍵によるイデアルのGroebner基底計算に適しており，事実，実験結果によるとMGBの方が効率的に計算を実行している．MPKCの評価にはFlよりもMGBを用いる方が適切である．