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
Masalah MinRank disiasat sebagai masalah yang berkaitan dengan serangan pangkat dalam kriptografi multivariate dan penyahkodan kod pangkat dalam teori pengekodan. Kaedah Kipnis-Shamir adalah salah satu kaedah untuk menyelesaikan masalah, dan baru-baru ini, kemajuan ketara telah dibuat dalam anggaran kerumitannya oleh Verbel et al. Memandangkan kaedah ini mengurangkan masalah kepada masalah MQ, yang meminta penyelesaian kepada sistem persamaan kuadratik, kerumitannya bergantung pada tahap penyelesaian sistem kuadratik yang disimpulkan daripada kaedah tersebut. Nilai teori yang diperkenalkan oleh Verbel et al. menghampiri tahap penyelesaian minimum sistem kuadratik dalam kaedah walaupun nilainya ditakrifkan di bawah had tertentu untuk sistem yang dipertimbangkan. Sistem kuadratik di luar hadnya selalunya mempunyai tahap penyelesaian yang lebih besar, tetapi kerumitan penyelesaian tidak selalu lebih tinggi kerana ia mempunyai bilangan pembolehubah dan persamaan yang lebih kecil. Oleh itu, untuk membincangkan kerumitan terbaik kaedah Kipnis-Shamir, nilai teori diperlukan untuk menganggarkan darjah penyelesaian setiap sistem kuadratik yang disimpulkan daripada kaedah tersebut. Sistem kuadratik yang disimpulkan daripada kaedah Kipnis-Shamir sentiasa mempunyai pelbagai darjah, dan kerumitan penyelesaian dipengaruhi oleh sifat ini. Dalam kajian ini, kami memperkenalkan nilai teori yang ditakrifkan oleh pelbagai darjah dan menunjukkan bahawa ia menghampiri darjah penyelesaian setiap sistem kuadratik. Oleh itu, sistem yang disimpulkan daripada kaedah dibandingkan, dan kerumitan terbaik dibincangkan. Sebagai aplikasi, untuk serangan MinRank menggunakan kaedah Kipnis-Shamir terhadap skim tandatangan multivariate Rainbow, kami menunjukkan kes di mana sistem kuadratik yang disimpulkan di luar had Verbel et al. adalah yang terbaik. Khususnya, anggaran kerumitan serangan MinRank menggunakan kaedah KS terhadap set parameter Rainbow I, III dan V dikurangkan sebanyak kira-kira 172, 140 dan 212 bit, masing-masing, daripada anggaran 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.
Salinan
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
Salinan
@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},}
Salinan
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 -