TY - JOUR

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

AU - Nakamura, Shuhei

AU - Wang, Yacheng

AU - Ikematsu, Yasuhiko

N1 - Funding Information:
This work was supported by JST CREST Grant Number JP-MJCR2113, JSPS KAKENHI Grant Number JP19K20266, JP20K19802.
Publisher Copyright:
© 2023 The Institute of Electronics.

PY - 2023/3

Y1 - 2023/3

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

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

UR - http://www.scopus.com/inward/record.url?scp=85150441334&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85150441334&partnerID=8YFLogxK

U2 - 10.1587/transfun.2022CIP0014

DO - 10.1587/transfun.2022CIP0014

M3 - Article

AN - SCOPUS:85150441334

SN - 0916-8508

VL - 106 EA

SP - 203

EP - 211

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 3

ER -