Recent progress in the security evaluation of multivariate public-key cryptography

Yasuhiko Ikematsu, Shuhei Nakamura, Tsuyoshi Takagi

Research output: Contribution to journalReview articlepeer-review

3 Citations (Scopus)


Multivariate public-key cryptography (MPKC) is considered a leading candidate for post-quantum cryptography (PQC). It is based on the hardness of the multivariate quadratic polynomial (MQ) problem, which is a problem of finding a solution to a system of quadratic equations over a finite field. In this paper, we survey some recent progress in the security analysis of MPKC. Among various existing multivariate schemes, the most important one is the Rainbow signature scheme proposed by Ding et al. in 2005, which was later selected as a finalist in the third round of the PQC standardization project by the National Institute of Standards and Technology. Under the circumstances, some recent research studies in MPKC have focussed on the security analysis of the Rainbow scheme. In this paper, the authors first explain efficient algorithms for solving the MQ problem and the research methodology for estimating their complexity in MPKC. Then, the authors survey some recent results related to the security analysis of the Rainbow scheme. In particular, the authors provide a detailed description of the complexity analysis for solving the bi-graded polynomial systems studied independently by Nakamura et al. and Smith-Tone et al., and then expound the rectangular MinRank attack against Rainbow proposed by Beullens.

Original languageEnglish
Pages (from-to)210-226
Number of pages17
JournalIET Information Security
Issue number2
Publication statusPublished - Mar 2023

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Recent progress in the security evaluation of multivariate public-key cryptography'. Together they form a unique fingerprint.

Cite this