Abstract 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.

At SAC2017, Akiyama et al. proposed the indeterminate equation encryption scheme whose security is based on a solution problem of indeterminate equation. It is an extension of algebraic surface encryption scheme. A public key X for this scheme is a polynomial in two variables over a finite ring. Akiyama et al. also proposed two attacks, the linear algebraic attack (LAA) and the key recovery attack (KRA), by using the lattice structure associated with this scheme. In this paper, we give an improvement on LAA. Also we explain the relation between our improvement and the improvement on LAA proposed by Xagawa and examine parameters that those attacks fail by experiments. As a result, we conclude that if the total degree of the public key X is one, then KRA is more efficient than LAA and if that of X is two, then LAA is more efficient than KRA.