高木 剛 |
題名:MQ Challenge: 多変数多項式暗号の安全性評価 |
アブストラクト:
多変数2次多項式の求解問題(MQ問題)は、
多変数多項式暗号の安全性の根拠として利用されている数学
問題である。MQ問題の難しさは、変数の数n、多項式の数m、
有限体の位数qなどにより変化する。我々は、MQ問題の計算
量的困難性を評価するために、MQ Challengeを2015年4月1日
から開始する予定である。多変数多項式の暗号化で用いら
れるパラメータとしてm=2n, 署名方式に対してはn~1.5m、
更に有限体としてはGF(2), GF(2^8), GF(31)を選択した。
これらの解読問題により、MQ問題の困難性をより正確に
見積もることができ、多変数多項式暗号を安全に利用
できるパラメータの選択が可能となる。
キーワード: MQ問題、ポスト量子暗号、多変数多項式暗号 |
Tsuyoshi Takagi |
Title: MQ Challenge: Security Evaluation of Multivariate PKC |
Abstract:
Multivariate Quadratic (MQ) polynomial problem is the
basis of security for potentially post-quantum cryptosystems.
The hardness of solving MQ problem depends on a number of
parameters, most importantly the number of variables and the
number of equations as well as the size of the base field etc.
We investigate the relation among these parameters and the
hardness of solving MQ problem, in order to construct hard
instances of MQ problem. These instances are used to create
a challenge, which may be helpful in determining appropriate
parameters for multivariate public key cryptosystems, and
stimulate furthermore the research in solving MQ problem.
Keywords: MQ problem, Post-quantum cryptography, Multivariate public key cryptosystems |