Cryptology ePrint Archive: Report 2015/275
MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems
Takanori Yasuda and Xavier Dahan and Yun-Ju Huang and Tsuyoshi Takagi and Kouichi Sakurai
Abstract: Multivariate Quadratic polynomial (MQ) problem serve as 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 degree of the
polynomials, as well as the number of equations, 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 further the research in
solving MQ problem.
Category / Keywords: public-key cryptography / post-quantum cryptography, multivariate public-key cryptosystem, MQ problem
Date: received 23 Mar 2015, last revised 28 May 2015
Contact author: yasuda at isit or jp
Available format(s): PDF | BibTeX Citation
Note: Revised version contains description of the range of parameters of MQ challenge and correction of errors.
Version: 20150529:021857 (All versions of this report)
Short URL: ia.cr/2015/275
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]