A New Analysis of the Kipnis-Shamir Method Solving the MinRank Problem

The MinRank problem is investigated as a problem related to rank attacks in multivariate cryptography and the decoding of rank codes in coding theory. The Kipnis-Shamir method is one of the methods to solve the problem, and recently, significant progress has been made in its complexity estimation by Verbel et al. As this method reduces the problem to an MQ problem, which asks for a solution to a system of quadratic equations, its complexity depends on the solving degree of a quadratic system deduced from the method. A theoretical value introduced by Verbel et al. approximates the minimal solving degree of the quadratic systems in the method although their value is defined under a certain limit for the system considered. A quadratic system outside their limitation often has a larger solving degree, but the solving complexity is not always higher because it has a smaller number of variables and equations. Thus, in order to discuss the best complexity of the Kipnis-Shamir method, a theoretical value is needed to approximate the solving degree of each quadratic system deduced from the method. A quadratic system deduced from the Kipnis-Shamir method always has a multi-degree, and the solving complexity is influenced by this property. In this study, we introduce a theoretical value defined by such a multi-degree and show that it approximates the solving degree of each quadratic system. Thus, the systems deduced from the method are compared, and the best complexity is discussed. As an application, for the MinRank attack using the Kipnis-Shamir method against the multivariate signature scheme Rainbow, we show a case in which a deduced quadratic system outside Verbel et al.'s limitation is the best. In particular, the complexity estimation of the MinRank attack using the KS method against the Rainbow parameter sets I, III and V is reduced by about 172, 140 and 212 bits, respectively, from Verbel et al.'s estimation.