| 講演名 | 2011-05-13 非可換環上の多変数多項式署名方式に対する安全性評価の再考 安田 貴徳, 櫻井 幸一, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 1984年、Ong-Shnorr-Shamirは2元2次多項式を用いた電子署名方式を考案した。この方式はRSA暗号同様に素因数分解の困難性に安全性の根拠を置くものであったが、新たな方程式解法アルゴリズムの開発により破られた。その後このOSS署名は2方向に拡張された。一つはShamirによるBirational Permutation方式で変数が多変数化される。もう一つは佐藤-荒木により、非可換環を利用するものである。しかし、これら2つに対しても、それぞれ効果的な攻撃方法が見つけられた。2008年、橋本-櫻井はこれら2つの特徴を取り込み、かつそれらに有効であった攻撃方法に対し安全である新たな署名方式(HS署名方式)を考案した。HS署名では、高次数の行列を利用し、2次元の特殊な場合が佐藤-荒木書名となる。ところが、内山-小椋はHS署名がRainbowに書き換えられることを指摘し、小さいサイズの場合Rainbowへの攻撃を用いて署名偽造の可能性を論じた。本稿ではHS署名方式を多変数公開鍵暗号の一部として再定義し、法が合成数でない場合でも適用可能な耐量子パラダイムを展開する。さらに安全性について再考する。とくに、内山-小椋攻撃の限界や他の解読手法への耐性を解析し、パラメータの取り方さえ注意すればHS署名はいまだ安全であることを主張する。 |
| 抄録(英) | In 1984, Ong-Shnorr-Shamir presented a digital signature scheme using quadratic polynomials with 2 variables. The security of this scheme was based on the difficulty of factorization of integers, but, broken by the exploit of new algorithm of solving system of equations. Then it was extended to two way of schemes. One is the Shamir's Birational signature scheme, which uses several variables. Another is the Sato-Araki signature scheme, which uses non-commutative rings. However efficient attacks has been also found against these schemes. In 2008, Hashimoto and Sakurai presented a signature scheme (HS signature scheme) which contains property of the above two scheme and is secure against the attacks effective for them. However, Uchiyama and Ogura pointed out that the HS signature scheme is rewritten by the Rainbow and discussed the possibility of forgery for the scheme with a small parameter by an attack available for the Rainbow. In this paper, we redefine the HS signature scheme as a part of Multivariate Public Key Cryotosystems. In addition, we revisit its security and insist that the HS signature is secure as long as we pay attention to a choice of parameters. |
| キーワード(和) | 電子署名 / 多変数公開鍵暗号 / OSS署名方式 / Rainbow / 非可換環 / ポスト量子暗号 |
| キーワード(英) | Digital signature / Multivariate public key cryptosystems / OSS signature scheme / Post-quantum cryptography |
| 資料番号 | ISEC2011-1 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2011/5/6(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 非可換環上の多変数多項式署名方式に対する安全性評価の再考 |
| サブタイトル（和） | |
| タイトル（英） | Revisited: Security of multivariate polynomial signatures over non-commutative rings |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 電子署名 / Digital signature |
| キーワード(2)（和/英） | 多変数公開鍵暗号 / Multivariate public key cryptosystems |
| キーワード(3)（和/英） | OSS署名方式 / OSS signature scheme |
| キーワード(4)（和/英） | Rainbow / Post-quantum cryptography |
| キーワード(5)（和/英） | 非可換環 |
| キーワード(6)（和/英） | ポスト量子暗号 |
| 第 1 著者 氏名（和/英） | 安田 貴徳 / Takanori YASUDA |
| 第 1 著者 所属（和/英） | 九州先端科学技術研究所 Institute of Systems, Information Technologies and Nanotechnologies |
| 第 2 著者 氏名（和/英） | 櫻井 幸一 / Kouichi SAKURAI |
| 第 2 著者 所属（和/英） | 九州先端科学技術研究所:九州大学大学院システム情報科学研究院 Institute of Systems, Information Technologies and Nanotechnologies:Department of Informatics, Kyushu University |
| 発表年月日 | 2011-05-13 |
| 資料番号 | ISEC2011-1 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | 34 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |