Paper 2020/908

Analysis on the MinRank Attack using Kipnis-Shamir Method Against Rainbow

Shuhei Nakamura, Yacheng Wang, and Yasuhiko Ikematsu

Abstract

Minrank problem is investigated as a problem related to a rank attack in multivariate cryptography and decoding of a rank code in coding theory. Recently, the Kipnis-Shamir method for solving this problem has been made significant progress due to Verbel et al. As this method reduces the problem to the MQ problem that asks for a solution of 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 a considering system. A quadratic system outside their limitation often has the larger solving degree, but its solving complexity is not necessary larger since it has a smaller number of variables and equations. Thus, in order to discuss the best complexity of the Kipnis-Shamir method, we need a theoretical value approximating the solving degree of each deduced quadratic system. A quadratic system deduced from the Kipnis-Shamir method has a multi-degree always, and its solving complexity is influenced by this property. In this paper, we introduce a theoretical value defined by such a multi-degree and show it approximates the solving degree of each quadratic system. Thus we are able to compare the systems in the method and to discuss the best complexity. As its application, in the Minrank problem from the rank attack using the Kipnis-Shamir method against Rainbow, we show a case that a quadratic system outside Verbel et al.'s limitation is the best. Consequently, by using our estimation, the complexities of the attack against Rainbow parameter sets Ia, IIIc and Vc are improved as $2^{160.6}, 2^{327.9}$ and $2^{437.0}$, respectively.