Paper 2015/275

MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems

Takanori Yasuda, Xavier Dahan, Yun-Ju Huang, 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.

Note: Revised version contains description of the range of parameters of MQ challenge and correction of errors.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
post-quantum cryptographymultivariate public-key cryptosystemMQ problem
Contact author(s)
yasuda @ isit or jp
History
2015-05-29: last of 4 revisions
2015-03-25: received
See all versions
Short URL
https://ia.cr/2015/275
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/275,
      author = {Takanori Yasuda and Xavier Dahan and Yun-Ju Huang and Tsuyoshi Takagi and Kouichi Sakurai},
      title = {MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2015/275},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/275}},
      url = {https://eprint.iacr.org/2015/275}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.