| 講演名 | 2020-05-20 ［招待講演］F4-styleアルゴリズムによるMQ問題の求解 (from IWSEC 2019) 伊藤 琢真(NICT), 篠原 直行(NICT), 内山 成憲(都立大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本講演ではIWSEC 2019で発表した論文“An Efficient F4-style Based Algorithm to Solve MQ Problems”を紹介する. MQ問題とは連立二次多変数代数方程式の解を求める問題であり, 耐量子計算機暗号の候補である多変数公開暗号の安全性はMQ問題を解く計算の困難性に依存している. MQ問題の計算困難性を評価するためにFukuoka MQ challengeというプロジェクトが幾つかのMQ問題を出題している. MQ問題を解くためにGrobner基底を計算する方法がよく用いられ, 代表的なアルゴリズムとしてはF4やM4GBなどがある. 今回我々はF4-style アルゴリズムを用いてMQ問題を効率的に解く手法を提案し, Fukuoka MQ challengeの問題を解くことについて世界記録を更新することに成功した. |
| 抄録(英) | We introduce “An Efficient F4-style Based Algorithm to Solve MQ Problems”we presented in IWSEC 2019. |
| キーワード(和) | 多変数公開鍵暗号 / MQ問題 / Gr?bner基底 / F4-style アルゴリズム / 耐量子計算機暗号 |
| キーワード(英) | Multivariate public key cryptosystems / Multivariate quadratic problem / Gr?bner basis / F4-style algorithm / Post-quantum cryptography |
| 資料番号 | ISEC2020-5 |
| 発行日 | 2020-05-13 (ISEC) |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2020/5/20(から1日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 委員長氏名（和） | 盛合 志帆(NICT) |
| 委員長氏名（英） | Shiho Moriai(NICT) |
| 副委員長氏名（和） | 廣瀬 勝一(福井大) / 伊豆 哲也(富士通研) |
| 副委員長氏名（英） | Shoichi Hirose(Univ. of Fukui) / Tetsuya Izu(Fujitsu Labs.) |
| 幹事氏名（和） | 江村 恵太(NICT) / 面 和成(筑波大) |
| 幹事氏名（英） | Keita Emura(NICT) / Kazunari Omote(Tsukuba Univ.) |
| 幹事補佐氏名（和） | 山本 大(富士通研) / 須賀 祐治(インターネットイニシアティブ) |
| 幹事補佐氏名（英） | Dai Yamamoto(Fujitsu Labs.) / Yuuji Suga(IIJ) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Security |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ［招待講演］F4-styleアルゴリズムによるMQ問題の求解 (from IWSEC 2019) |
| サブタイトル（和） | |
| タイトル（英） | [Invited Talk] An Efficient F4-style Based Algorithm to Solve MQ Problems (from IWSEC 2019) |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 多変数公開鍵暗号 / Multivariate public key cryptosystems |
| キーワード(2)（和/英） | MQ問題 / Multivariate quadratic problem |
| キーワード(3)（和/英） | Gr?bner基底 / Gr?bner basis |
| キーワード(4)（和/英） | F4-style アルゴリズム / F4-style algorithm |
| キーワード(5)（和/英） | 耐量子計算機暗号 / Post-quantum cryptography |
| 第 1 著者 氏名（和/英） | 伊藤 琢真 / Takuma Ito |
| 第 1 著者 所属（和/英） | 情報通信研究機構(略称：NICT) National Institute of Information and Communications Technology(略称：NICT) |
| 第 2 著者 氏名（和/英） | 篠原 直行 / Naoyuki shinohara |
| 第 2 著者 所属（和/英） | 情報通信研究機構(略称：NICT) National Institute of Information and Communications Technology(略称：NICT) |
| 第 3 著者 氏名（和/英） | 内山 成憲 / Shigenori Uchiyama |
| 第 3 著者 所属（和/英） | 東京都立大学(略称：都立大) Tokyo Metropolitan University(略称：TMU) |
| 発表年月日 | 2020-05-20 |
| 資料番号 | ISEC2020-5 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | ISEC-28 |
| ページ範囲 | pp.25-25(ISEC), |
| ページ数 | 1 |
| 発行日 | 2020-05-13 (ISEC) |