The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
O problema MinRank é investigado como um problema relacionado a ataques de classificação em criptografia multivariada e à decodificação de códigos de classificação na teoria da codificação. O método Kipnis-Shamir é um dos métodos para resolver o problema e, recentemente, progressos significativos foram feitos na sua estimativa de complexidade por Verbel et al. Como este método reduz o problema a um problema MQ, que pede uma solução para um sistema de equações quadráticas, a sua complexidade depende do grau de resolução de um sistema quadrático deduzido do método. Um valor teórico introduzido por Verbel et al. aproxima o grau mínimo de resolução dos sistemas quadráticos no método embora seu valor seja definido sob um certo limite para o sistema considerado. Um sistema quadrático fora de suas limitações geralmente possui um grau de resolução maior, mas a complexidade de resolução nem sempre é maior porque possui um número menor de variáveis e equações. Assim, para discutir a melhor complexidade do método Kipnis-Shamir, é necessário um valor teórico para aproximar o grau de resolução de cada sistema quadrático deduzido do método. Um sistema quadrático deduzido do método Kipnis-Shamir sempre possui multigraus, e a complexidade da resolução é influenciada por esta propriedade. Neste estudo, introduzimos um valor teórico definido por tal multigrau e mostramos que ele se aproxima do grau de resolução de cada sistema quadrático. Assim, os sistemas deduzidos do método são comparados e a melhor complexidade é discutida. Como aplicação, para o ataque MinRank utilizando o método Kipnis-Shamir contra o esquema de assinatura multivariada Rainbow, mostramos um caso em que um sistema quadrático deduzido fora da limitação de Verbel et al. Em particular, a estimativa da complexidade do ataque MinRank usando o método KS contra os conjuntos de parâmetros Rainbow I, III e V é reduzida em cerca de 172, 140 e 212 bits, respectivamente, da estimativa de Verbel et al.
Shuhei NAKAMURA
Nihon University
Yacheng WANG
Corporate Research & Development Center Toshiba
Yasuhiko IKEMATSU
Kyushu University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Shuhei NAKAMURA, Yacheng WANG, Yasuhiko IKEMATSU, "A New Analysis of the Kipnis-Shamir Method Solving the MinRank Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 3, pp. 203-211, March 2023, doi: 10.1587/transfun.2022CIP0014.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022CIP0014/_p
Copiar
@ARTICLE{e106-a_3_203,
author={Shuhei NAKAMURA, Yacheng WANG, Yasuhiko IKEMATSU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A New Analysis of the Kipnis-Shamir Method Solving the MinRank Problem},
year={2023},
volume={E106-A},
number={3},
pages={203-211},
abstract={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.},
keywords={},
doi={10.1587/transfun.2022CIP0014},
ISSN={1745-1337},
month={March},}
Copiar
TY - JOUR
TI - A New Analysis of the Kipnis-Shamir Method Solving the MinRank Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 203
EP - 211
AU - Shuhei NAKAMURA
AU - Yacheng WANG
AU - Yasuhiko IKEMATSU
PY - 2023
DO - 10.1587/transfun.2022CIP0014
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2023
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.
ER -