The complexity of the SupportMinors Modeling for the MinRank Problem

Daniel Cabarcas, Giulia Gaggero, Elisa Gorla · 2025

Read The complexity of the SupportMinors Modeling for the MinRank Problem by Daniel Cabarcas, Giulia Gaggero, Elisa Gorla (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06547.txt.

Introduction

Daniel Cabarcas, Giulia Gaggero, and Elisa Gorla wrote a short 2025 note on the cost of a modeling method for a hard algebra problem. The problem, called MinRank, asks for a matrix of low rank hidden in a set of matrices, and it backs the security of some proposed codes. One attack models the problem with extra variables for small matrix blocks. The note supplies proven estimates for how costly that modeling runs, mostly confirming the rough guesses given in the paper that first proposed it.

Catalog record

CREATORDaniel Cabarcas, Giulia Gaggero, Elisa Gorla
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-06547

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The complexity of the SupportMinors Modeling for the MinRank Problem Daniel Cabarcas, Giulia Gaggero, Elisa Gorla Abstract In this note, we provide proven estimates for the complexity of the SupportMinors Modeling, mostly confirming the heuristic complexity estimates contained in the original article. 1 Introduction The MinRank Problem arises naturally within cryptography and coding theory, as well as in numerous other applications. The problem in its general form can be stated as follows. MinRank Problem . Let \mathbb{K} be a field and let m,n,k be positive integers. Given as input K matrices M_{1},\dots,M_{K}\in\mathbb{K}^{n\times m} , find x_{1},\dots,x_{K}\in\mathbb{K} such that the matrix \sum_{\ell=1}^{k}x_{\ell}M_{\ell} is nonzero and has least possible rank. In situations when the least possible rank (or a tight upper bound for it) is known, one may rephrase the problem as follows. MinRank Problem . Let \mathbb{K} be a field and let m,n,r,k be positive integers. Given as input K matrices M_{1},\dots,M_{K}\in\mathbb{K}^{n\times m} , find x_{1},\dots,x_{K}\in\mathbb{K} such that 0<\rk\left(\sum_{\ell=1}^{K}x_{\ell}M_{\ell}\right)\leq r. The MinRank Problem plays a central role within multivariate cryptography, both in the cryptanalysis and in the design of schemes, as it is NP-complete [ 19 ] and believed to be quantum-resistant. For example, it is a central tool in the cryptanalysis of HFE and its variants [ 33 , 14 , 20 , 45 , 24 ] , the TTM Cryptosystem [ 32 ] , and the ABC Cryptosystem [ 40 , 41 ] . More recently, both GeMSS and Rainbow were subject to attacks which exploit the MinRank Problem, see [ 15 , 44 , 8 , 16 ] . On the constructive side, a zero-knowledge protocol based on the MinRank Problem was proposed by Courtois in [ 23 ] . This produces a signature scheme following [ 29 ] . Recently, a scheme relying on the MinRank Problem for its security was proposed in [ 43 ] and cracked in [ 17 ] . Digital signature relying on the MinRank Problem for their security were submitted to the NIST Call for Additional Digital Signature Schemes in 2023 [ 1 , 4 ] , see also [ 12 ] . In addition, the MinRank Problem is closely related to Minimum Distance Decoding in the rank-metric. Notice in fact that, if \mathcal{C}\subseteq\mathbb{K}^{n\times m} is a linear rank-metric code with basis M_{1},\dots,M_{K}\in\mathbb{K}^{n\times m} and minimum distance d(\mathcal{C}) , then Minimum Distance Decoding in the rank-metric can be phrased as follows. Minimum Rank-Distance Decoding . Given a received matrix M_{0}\in\mathbb{K}^{n\times m} and a basis M_{1},\dots,M_{K}\in\mathbb{K}^{n\times m} of the code \mathcal{C} , find x_{1},\dots,x_{K}\in\mathbb{K} such that \rk\left(\sum_{\ell=1}^{K}x_{\ell}M_{\ell}-M_{0}\right)\leq\frac{d(\mathcal{C})-1}{2}. One sees immediately that Minimum Rank-Distance Decoding is an instance of the MinRank Problem in its second formulation. Therefore, estimates on the complexity of the MinRank Problem have a direct impact on understanding the complexity of decoding a general code with respect to the rank-metric and hence on complexity estimates in rank-metric code-based cryptography. Similarly to the MinRank Problem, Minimum Rank-Distance Decoding is known to be NP-hard [ 23 ] and believed to be quantum-resistant. Rank-metric code-based cryptography may be traced back to [ 30 ] , where Gabidulin codes were used. The weakness of this proposal and of some related attempts were later exposed in [ 42 , 28 , 13 , 36 ] . Rank-metric code-based cryptography has become relevant again in recent years, when several new cryptographic schemes based on Minimum Rank-Distance Decoding were proposed in the context of the NIST Post-Quantum Cryptography Standardization process, see [ 5 , 6 , 38 , 37 , 39 , 31 , 7 ] . While none of these proposals was selected, NIST expressed interest in further study of rank-based cryptosystems. In addition, two digital signatures [ 22 , 3 ] which base their security on Minimum Rank-Distance Decoding were submitted this year to the NIST Call for Additional Digital Signature Schemes. Main modelings for the MinRank Problem are the Kipnis-Shamir [ 33 ] and the Minors Modeling [ 27 , 25 , 26 , 21 ] . In the past few years, variations of the Minors Modeling such as the MaxMinors Modeling [ 10 ] and the SupportMinors Modeling [ 11 , 9 ] were introduced. Their advantage is that experimentally they appear to have significantly lower complexity compared to the classical Minors Modeling. However, their complexity is significantly less well-understood and current estimates heavily rely on heuristic assumptions. This work aims at making the heuristics of [ 11 ] rigorous, therefore establishing a rigorous upper bound on the complexity of MinRank. In Section 2 , we fix the notation and review some preliminaries that will be used throughout the paper. In Section 3 we study the algebraic situation in which the entries of the matrix are distinct variables. The results obtained in Section 3 are used in Section 4 , where we treat the general case. Our main result is Theorem 5 , where we compute the dimension of the vector space of relations among the rows of the Macaulay matrix used in the SupportMinors Algorithm. Using the results from the previous sections, in Section 5 we provide rigorous estimates for the complexity of the SupportMinors Modeling. Our findings mostly confirm the heuristic estimates from [ 11 ] . 2 Preliminaries and notation Let \mathbb{K} be a field and let r,m,n,K be positive integers, r\leq n . For a positive integer t , denote by [t] the set \{1,\ldots,t\} . For a square matrix M , denote by |M| the determinant of M . Throughout the paper, we work in the polynomial rings R=\mathbb{K}[y_{kj},c_{ij}:k\in[m],i\in[r],j\in[n]]\mbox{ and }P=\mathbb{K}[x_{\ell},c_{ij}:\ell\in[K],i\in[r],j\in[n]], where x_{1},\ldots,x_{K} , y_{11},\ldots,y_{mn} , and c_{11},\ldots,c_{rn} are distinct variables. SupportMinors Consider an instance of the MinRank Problem M_{1},\ldots,M_{K} with target rank r\geq 1 and let M_{\mathbf{x}}=\sum_{\ell=1}^{K}x_{\ell}M_{\ell} . Let C=(c_{ij}) be an r\times n matrix whose entries are distinct variables. SupportMinors addresses the MinRank Problem by solving the polynomial system in x_{\ell} and c_{ij} consisting of the equations \left\{\left|\begin{pmatrix}r_{i}\\ C\end{pmatrix}\right|_{*,J}:J\subseteq[n],\left\lvert J\right\rvert=r+1,r_{i}\text{ $i$-th row of }M_{\mathbf{x}},i\in[r]\right\}. (1) Here we denote by |M|_{*,J} the maximal minor of M corresponding to the columns indexed by J . Notice that each entry of M_{\mathbf{x}} is a linear form m_{kj}(\mathbf{x})=\sum_{\ell=1}^{K}m^{\ell}_{kj}x_{\ell} , where m^{\ell}_{kj} is the entry of M_{\ell} in position (k,j) . In order to study system ( 1 ), in Section 3 we analyze the simpler situation when the matrix M_{\mathbf{x}}=(m_{kj}(\mathbf{x})) is replaced by the matrix Y=(y_{kj}) , whose entries are distinct variables. Let D=\begin{pmatrix}Y\\ C\end{pmatrix}. Let \mathcal{F}\subseteq R be the set of the (r+1) -minors of D and let \mathcal{G} be the set of (r+1) -minors of D that involve the last r rows. In Section 4 , we apply the results of Section 3 to the study of the SupportMinors system ( 1 ). For that, let \rho:R\rightarrow P be the R -algebra homomorphism defined by c_{ij}\mapsto c_{ij} and y_{kj}\mapsto m_{kj}(\mathbf{x}) . Abusing notation, we denote by \rho also the homomorphism R^{t}\rightarrow P^{t} , t\in\mathbb{N} , that acts as \rho componentwise. We often use specializing as a synonym for computing the image of an object via \rho . Then \rho(D)=\begin{pmatrix}M_{\mathbf{x}}\\ C\end{pmatrix} and \rho(\mathcal{G}) coincides with ( 1 ). Let I\subseteq[m+r] and J\subseteq[n] be multisets with |I|=|J| . Throughout the paper, we abuse notation and write that a multiset is included

Read the complete text