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

摘要

多変数公開鍵暗号の安全性を評価するためには，公開鍵と暗号文による連立方程式を解く攻撃が最も汎用的である．このために使われる手法はグレブナー基底計算であり，通常はF_4アルゴリズムが使われている．理由は，数式処理システムに実装されているアルゴリズムの中ではF_4が最も高速であるためである．しかし，最近提案されたMutant Grobner Bases （MGB）アルゴリズムはMPKC公開鍵によるイデアルのGrobner基底計算に適しており，事実，実験結果によるとMGBの方が効率的に計算を実行している．MPKCの評価にはF_4よりもMGBを用いる方が適切である．