非可換環上の多変数多項式署名方式に対する安全性評価の再考

概要

論文の詳細を見る
1984年、Ong-Shnorr-Shamirは2元2次多項式を用いた電子署名方式を考案した。この方式はRSA暗号同様に素因数分解の困難性に安全性の根拠を置くものであったが、新たな方程式解法アルゴリズムの開発により破られた。その後このOSS署名は2方向に拡張された。一つはShamirによるBirational Permutation方式で変数が多変数化される。もう一つは佐藤-荒木により、非可換環を利用するものである。しかし、これら2つに対しても、それぞれ効果的な攻撃方法が見つけられた。2008年、橋本-櫻井はこれら2つの特徴を取り込み、かつそれらに有効であった攻撃方法に対し安全である新たな署名方式(HS署名方式)を考案した。HS署名では、高次数の行列を利用し、2次元の特殊な場合が佐藤-荒木書名となる。ところが、内山-小椋はHS署名がRainbowに書き換えられることを指摘し、小さいサイズの場合Rainbowへの攻撃を用いて署名偽造の可能性を論じた。本稿ではHS署名方式を多変数公開鍵暗号の一部として再定義し、法が合成数でない場合でも適用可能な耐量子パラダイムを展開する。さらに安全性について再考する。とくに、内山-小椋攻撃の限界や他の解読手法への耐性を解析し、パラメータの取り方さえ注意すればHS署名はいまだ安全であることを主張する。
2011-05-06

非可換環上の多変数多項式署名方式に対する安全性評価の再考

スポンサーリンク

概要

著者

関連論文

スポンサーリンク