平成27年3月 先端暗号フロンティアセミナー アブストラクト

高木 剛
題名: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問題、ポスト量子暗号、多変数多項式暗号

The 6th Meeting for Cryptology Frontier Group Abstract


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

[Back ]