講演抄録/キーワード |
講演名 |
2020-05-20 13:10
[招待講演]F4-styleアルゴリズムによるMQ問題の求解 (from IWSEC 2019) ○伊藤琢真・篠原直行(NICT)・内山成憲(都立大) ISEC2020-5 |
抄録 |
(和) |
本講演では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 / / / |
文献情報 |
信学技報, vol. 120, no. 28, ISEC2020-5, pp. 25-25, 2020年5月. |
資料番号 |
ISEC2020-5 |
発行日 |
2020-05-13 (ISEC) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ISEC2020-5 |