# Revisiting Algebraic Attacks on MinRank and on the Rank Decoding Problem

Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, Jean-Pierre Tillich

► To cite this version:

Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, Jean-Pierre Tillich. Revisiting Algebraic Attacks on MinRank and on the Rank Decoding Problem. Designs, Codes and Cryptography, 2023, 10.1007/s10623-023-01265-x. hal-04193709

HAL Id: hal-04193709

https://hal.science/hal-04193709v1

Submitted on 1 Sep 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Revisiting Algebraic Attacks on MinRank and
on the Rank Decoding Problem

Magali Bardet¹,², Pierre Briaud¹,³, Maxime Bros⁴, Philippe Gaborit⁴, and
Jean-Pierre Tillich¹

¹ Inria, 2 rue Simone Iff, 75012 Paris, France

² LITIS, University of Rouen Normandie, France

³ Sorbonne Universités, UPMC Univ Paris 06

pierre.briaud@inria.fr

⁴ Univ. Limoges, CNRS, XLIM, UMR 7252, F-87000 Limoges, France

maxime.bros@unilim.fr

**Abstract.** The Rank Decoding problem (RD) is at the core of rank-based cryptography. Cryptosystems such as ROLLO and RQC, which made it to the second round of the NIST Post-Quantum Standardization Process, as well as the Durandal signature scheme, rely on it or its variants. This problem can also be seen as a structured version of MinRank, which is ubiquitous in multivariate cryptography. Recently, [16,17] proposed attacks based on two new algebraic modelings, namely the MaxMinors modeling which is specific to RD and the Support-Minors modeling which applies to MinRank in general. Both improved significantly the complexity of algebraic attacks on these two problems. In the case of RD and contrarily to what was believed up to now, these new attacks were shown to be able to outperform combinatorial attacks and this even for very small field sizes.

However, we prove here that the analysis performed in [17] for one of
these attacks which consists in mixing the MaxMinors modeling with
the Support-Minors modeling to solve RD is too optimistic and leads to
underestimate the overall complexity. This is done by exhibiting linear
dependencies between these equations and by considering an $F_{q^m}$ version
of these modelings which turns out to be instrumental for getting a better
understanding of both systems. Moreover, by working over $F_{q^m}$ rather
than over $F_q$, we are able to drastically reduce the number of variables
in the system and we (i) still keep enough algebraic equations to be able
to solve the system, (ii) are able to analyze rigorously the complexity
of our approach. This new approach may improve the older MaxMinors
approach on RD from [16,17] for certain parameters. We also introduce
a new hybrid approach on the Support-Minors system whose impact
is much more general since it applies to any MinRank problem. This
technique improves significantly the complexity of the Support-Minors
approach for small to moderate field sizes.

**Keywords:** Post-quantum cryptography · NIST-PQC candidates · rank metric code-based cryptography · algebraic attack.
# 1 Introduction

**Rank Metric Code-based Cryptography.** Code-based cryptography using the rank metric, rank-based cryptography for short, started 30 years ago with the GPT cryptosystem [35] based on Gabidulin codes [34]. These codes can be viewed as analogues of Reed-Solomon codes in the rank metric, where polynomials are replaced by linearized polynomials. However this proposal and its variants were attacked with the Overbeck attack [49], much in the same way as McEliece schemes based on Reed-Solomon codes (or variants of them) have been attacked in [51,30].

Still, these attacks really exploited the strong algebraic structure of Gabidulin codes and did not rule out obtaining a secure version of the McEliece cryptosystem for the rank metric as we will see. One of the nice features of this metric is that it allows to exploit, in a much better way than the Hamming metric, codes which are linear over a very large extension field $F_{q^m}$. Indeed, assume that we could come up with a code family which is able to decode a linear number of errors in the code length $n$ and which would remain secure when used in a McEliece scheme. In the Hamming metric, the best algorithms for solving the decoding problem for a generic linear code are exponential in this regime in $n$, whereas they are exponential in $m \cdot n$ in the case of the rank metric. This would give cryptosystems with much smaller keysize in the rank metric case, which somehow mitigates the main drawback of the original McEliece proposal that is its large keysize. This dependency of the complexity exponent in the two parameters $m$ and $n$ also allows for much finer tuning of the parameters of such schemes.

A very significant step in this direction was made with the Low Rank Parity Check codes (LRPC) that were introduced in [37]. This type of codes made it possible to build McEliece schemes that can be viewed as the rank metric analogue of NTRU in the Euclidean metric [43] or of the MDPC cryptosystem in the Hamming metric [47], where the trapdoor is given by small weight vectors which allow efficient decoding. Contrarily to the GPT cryptosystem, this gives a cryptosystem whose security really relies on decoding an unstructured linear code and on distinguishing codes with moderate weight codewords from random linear codes. It can be argued that this second problem is similar in nature to the first one and so we have in a sense a cryptosystem whose security relies solely on the difficulty of generic decoding in the rank metric. This approach led to the design of several cryptosystems: [37,39,7,8], and in 2019, four rank-based schemes of this form [1,2,7,8] made it to the Second Round of the NIST Post-Quantum Standardization Process and were later merged into [9,4].

At the time of these submissions, the combinatorial attacks [48,38,12] were thought to be the most effective against these cryptosystems, especially for small values of $q$. However, it turned out later that algebraic attacks [16,17] could be improved a great deal and may be able to outperform the combinatorial attacks. This is the reason why these candidates were not kept for the Third Round, even if NIST still encourages further research on rank-based cryptography [6]. A first motivation is that these schemes still offer an interesting gain in terms
of public-key size due to the algebraic structure. Another one is that the use of
rank metric for wider cryptographic applications remains to be explored, and a
first challenging task would already be the design of a competitive code-based
signature scheme. Early attempts [11] based on the hash-and-sign paradigm and
on structural masking where broken [32]. More recently, a promising approach,
namely Durandal, adapting the Schnorr-Lyubashevsky framework to the rank
metric, was proposed [10]. Its security proof relies on the hardness of two prob-
lems: the first one is the decoding problem in the rank metric with multiple in-
stances sharing the same support (the so-called RSL problem), while the second
one is a new assumption called the Product Spaces Subspaces Indistinguish-
bility problem. The RSL problem was introduced in [36] and also studied in
[15]. It may become instrumental to build more efficient rank-based primitives
as shown by the recent work [5,24]. Finally, a third type of approach is to rely on
the famous Stern's Zero-Knowledge identification protocol [52], which is turned
into a signature scheme thanks to the Fiat-Shamir transform. The advantage
of this technique is that it only relies on the hardness of decoding a random
linear code: first, the security is well understood, and second one can use a seed
to generate the public key. This method has already inspired a long sequence
of optimizations and adaptations to the rank metric setting, see for instance
[40,18,21].

**Rank Decoding and MinRank Problems.** Codes used in rank metric cryp-
tography are linear codes over an extension field $\mathbb{F}_{q^m}$ of degree $m$ of $\mathbb{F}_q$. An
$\mathbb{F}_{q^m}$-linear code of length $n$ is an $\mathbb{F}_{q^m}$-linear subspace of $\mathbb{F}_{q^m}^n$, but its code-
words can also be viewed as matrices in $\mathbb{F}_q^{m \times n}$. Indeed, if $(\beta_1, \dots, \beta_m)$ is an
$\mathbb{F}_q$-basis of $\mathbb{F}_{q^m}$, the word $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{F}_{q^m}^n$ corresponds to the matrix
$\mathrm{Mat}(\mathbf{x}) = (X_{ij})_{i,j} \in \mathbb{F}_q^{m \times n}$, where $x_j = \beta_1 X_{1j} + \dots + \beta_m X_{mj}$ for $j \in \{1..n\}$.
The weight of $\mathbf{x}$ is then defined by using the underlying rank metric on $\mathbb{F}_q^{m \times n}$,
namely $|\mathbf{x}| := \mathrm{rk}(\mathrm{Mat}(\mathbf{x}))$, and it is also equal to the dimension of the support
$\mathrm{Supp}(\mathbf{x}) := \langle x_1, \dots, x_n \rangle_{\mathbb{F}_q}$. Similarly to the Hamming metric, the main source of
computational hardness for rank-based cryptosystems is a decoding problem. It
is the decoding problem in rank metric restricted to $\mathbb{F}_{q^m}$-linear codes, namely

*Problem 1* ((*m*, *n*, *k*, *r*) *Rank Decoding problem (RD)*).

The Rank Decoding problem of parameters (*m*, *n*, *k*, *r*) is given by

*Input:* an $\mathbb{F}_{q^m}$-linear subspace $C$ of $\mathbb{F}_{q^m}^n$, an integer $r \in \mathbb{N}$, and a vector $\mathbf{y} \in \mathbb{F}_{q^m}^n$ such that $|\mathbf{y} - \mathbf{c}| \le r$ for some $\mathbf{c} \in C$.

*Output:* $\mathbf{c} \in C$ and an error $\mathbf{e} \in \mathbb{F}_{q^m}^n$ such that $\mathbf{y} = \mathbf{c} + \mathbf{e}$ and $|\mathbf{e}| \le r$. We
call this an $(\mathbf{y}, C, r)$ instance of the RD problem.

**Remark 1.** From now on, we consider that the error **e** is of maximal weight
*r*. This can be done without loss of generality, since we can run the algebraic
attacks which follow for increasing values of *r'* ≤ *r* and since the most costly
part corresponds always to *r'* = *r*.

Given $\mathbf{s} \in \mathbb{F}_{q^m}^{n-k}$ and $\mathbf{H} \in \mathbb{F}_{q^m}^{(n-k) \times n}$ a parity-check matrix of an $\mathbb{F}_{q^m}$-linear code $C$, the syndrome version, denoted by RSD for *Rank Syndrome Decoding*,
asks to find $e \in \mathbb{F}_{q^m}^n$ such that $He^T = s^T$ and $|e| = r$, and it is equivalent to RD. Even if RD is not known to be NP-complete, there is a randomized reduction from RD to an NP-complete problem [41], namely to decoding in the Hamming metric. An RD instance can also be viewed as a structured instance of the following inhomogeneous MinRank problem.

**Problem 2 (Inhomogeneous (m, n, K, r) MinRank problem).**

The MinRank problem with parameters $(m, n, K, r)$ is given by

*Input*: an integer $r \in \mathbb{N}$ and $K + 1$ matrices $M_0, M_1, \dots, M_K \in \mathbb{F}_q^{m \times n}$.

*Output*: field elements $x_1, x_2, \dots, x_K \in \mathbb{F}_q$

$$ \mathrm{rk} \left( M_0 + \sum_{i=1}^{K} x_i M_i \right) = r. $$

More precisely, there exists a reduction from RD to the MinRank problem [33]. The latter was defined and proven NP-complete in [26], and it is now ubiquitous in multivariate cryptography [44,50,27,54,22,53,14,23]. In the cryptographically relevant regime, the current best known algorithms to solve it are algebraic attacks which all have exponential complexity.

**Solving RD.** First, note that owing to the aforementioned reduction [33], all the methods for solving MinRank can be applied to the RD problem. However, a plain MinRank solver would not be the most suitable as it forgets the $\mathbb{F}_{q^m}$-linear structure inherent to RD. In particular, the first attacks specific to the RD problem were of combinatorial nature [28]. They were significantly improved in [48] and further refined in [38,13]. These works can be viewed as the continuation of the former Goubin's kernel attack on generic MinRank [42], which consists of first guessing sufficiently many vectors in the kernel of the rank $r$ matrix and then solving a linear system. The considerable difference in the case of RD is that the success probability of this guess can be greatly increased thanks to the $\mathbb{F}_{q^m}$-linearity. Another way to solve RD is provided by algebraic attacks which are not plain MinRank attacks [45,38]. These techniques were considered to be less efficient than the combinatorial ones for a long time, especially for small values of $q$. In particular, the parameters of the rank based NIST submissions [7,8,2] were chosen according to the best combinatorial attacks. However, a breakthrough paper [16] showed how the $\mathbb{F}_{q^m}$-linear structure of the problem could be used to devise a dedicated and more efficient algebraic attack based on the so-called MaxMinors modeling. This was further improved in [17], which also introduced another algebraic modeling, the so-called Support-Minors modeling. Support-Minors is a generic MinRank modeling but it can be combined with MaxMinors in order to solve the RD problem. In particular, this thread of work contributed to significantly break the proposed parameters for ROLLO and RQC, and these rank-based schemes have not passed the Second Round of the NIST PQC competition.
The MaxMinors modeling [16,17]. The attack introduced in [16] relies on the following observations

- a vector $\mathbf{u} \in \mathbb{F}_{q^m}^n$ is of rank $r$ iff its entries generate a subspace of $\mathbb{F}_{q^m}$ of dimension $r$, say $\langle s_1, \dots, s_r \rangle_{\mathbb{F}_q}$. In such a case, there exists $\mathcal{C} \in \mathbb{F}_q^{r \times n}$ such that

$$ \mathbf{u} = (s_1, \dots, s_r)\mathcal{C}. $$

- Let $(\mathbf{c}, \mathbf{e})$ be the solution to RD. There exists $s_1, \dots, s_r \in \mathbb{F}_{q^m}$ and $\mathcal{C} \in \mathbb{F}_q^{r \times n}$ such that $\mathbf{y} - \mathbf{c} = (s_1, \dots, s_r)\mathcal{C}$, because $\mathbf{y} - \mathbf{c} = \mathbf{e}$ is of rank $\le r$. If we bring in a parity check matrix $\mathbf{H}_\mathbf{y} \in \mathbb{F}_{q^m}^{(n-k-1) \times n}$ of the extended code $\mathcal{C} + \langle \mathbf{y} \rangle$ then we have

$$ (s_1, \dots, s_r)\mathbf{CH}_\mathbf{y}^\top = 0. $$

This implies that the $r \times (n-k-1)$ matrix $\mathbf{CH}_\mathbf{y}^\top$ is not of full rank and that all its maximal minors are equal to 0. By using the Cauchy-Binet formula (3), each of these maximal minors can be expressed as a linear combination of the maximal minors $c_T$ of the matrix $\mathcal{C}$. Here $c_T$ denotes the maximal minor equal to the determinant of the square submatrix of $\mathcal{C}$ whose column indexes belong to $T \subset \{1..n\}$, $\#T = r$.

From there one readily obtains:

**Modeling 1 (MM-$\mathbb{F}_{q^m}$)**

$$ \text{MaxMinors}(\mathbf{CH}_\mathbf{y}^\top) = \left\{ P_J := \left| \mathbf{CH}_\mathbf{y}^\top \right|_{*,J} : J \subset \{1..n-k-1\}, \#J = r \right\} \quad (\text{MM-$\mathbb{F}_{q^m}$}) $$

**Unknowns:** $\binom{n}{r}$ variables $c_T := |\mathcal{C}|_{*,T}$, $T \subset \{1..n\}$, $\#T = r$, searched over $\mathbb{F}_q$, 
**Equations:** $\binom{n-k-1}{r}$ equations $P_J = 0$, $J \subset \{1..n-k-1\}$, $\#J = r$ viewed as linear equations over $\mathbb{F}_{q^m}$ in the $c_T$'s.

As these polynomials have coefficients in $\mathbb{F}_{q^m}$ while the $c_T$'s belong to $\mathbb{F}_q$, a standard approach is to consider a system with equations over the small field with the same solutions over $\mathbb{F}_q$. This is formalized in [17, Notation 2] with an operation<fnref n="5" /> which associates to a system $\mathcal{F} := \{f_1, \dots, f_M\} \subset \mathbb{F}_{q^m}[z_1, \dots, z_N]$ with coefficients in $\mathbb{F}_{q^m}$ a second system

$$ \text{Unfold}(\mathcal{F}) := \{f_{i,j} : 1 \le i \le m, 1 \le j \le M\} \in \mathbb{F}_q[\mathbf{z}]^{M \cdot m}, $$

such that for all $j \in \{1..M\}$ and $\mathbf{z} \in \mathbb{F}_q^N$, $f_j(\mathbf{z}) = 0 \Leftrightarrow (\forall i \in \{1..m\}, f_{i,j}(\mathbf{z}) = 0)$, and such that the variables involved are the same. Applying this procedure to MM-$\mathbb{F}_{q^m}$ yields Modeling 2, denoted MM-$\mathbb{F}_q$, which is the relevant one for the cryptographic attack:

<footnote n="5">⁵ a more canonical definition will be given in Section 2</footnote>
## Modeling 2 (MM-$\mathbb{F}_q$)

$$ \text{Unfold}(\text{MaxMinors}(\mathcal{CH}_y^T)) = \{P_{i,J} : i \in \{1..m\}, J \subset \{1..n-k-1\}, \#J = r\} \quad (\text{MM-$\mathbb{F}_q$}) $$

**Unknowns:** $\binom{n}{r}$ variables $c_T := |\mathcal{C}|_{*,T}$, $T \subset \{1..n\}$, $\#T = r$, searched over $\mathbb{F}_q$, 
**Equations:** $m\binom{n-k-1}{r}$ equations $P_{i,J} = 0$, which are linear over $\mathbb{F}_q$ in the $c_T$'s.

If $m\binom{n-k-1}{r} \ge \binom{n}{r} - 1$, the value of the $c_T$'s may be found by solving the linear system MM-$\mathbb{F}_q$. This is the so-called *overdetermined* case in [17]. Otherwise, in the *underdetermined* case, one can adopt a form of hybrid approach by adding random linear constraints on the variables to obtain another linear system that can be solved.

The Support-Minors modeling [17]. An alternative method in the underdetermined case is to rely on the Support-Minors modeling which was introduced in [17]. The Support-Minors modeling is a generic MinRank modeling which is not specific to the RD problem and which can be quite effective in a certain parameter range. In particular, it turned out to be instrumental for breaking the third round or alternate third round multivariate finalists Rainbow and GeMSS of the NIST competition [22,23,53,14]. Applied to the specific RD case, Support-Minors can be explained as follows. First, rewrite $\mathbf{y} - \mathbf{c} = (s_1, \dots, s_r)\mathcal{C}$ in a matrix form. On the one hand, the matrix Mat $((s_1, \dots, s_r)\mathcal{C})$ is readily seen to be equal to $\mathcal{SC}$ where $\mathcal{S} := \text{Mat}(s_1, \dots, s_r)$ and therefore we have

$$ \text{Mat}(\mathbf{y} + \mathbf{x}\mathcal{G}) = \mathcal{SC}, \quad (1) $$

where $\mathcal{G}$ is a generator matrix of $\mathcal{C}$, $\mathbf{x} = (x_1, \dots, x_k) \in \mathbb{F}_{q^m}^k$ and $-\mathbf{c} = \mathbf{x}\mathcal{G}$. On the other hand, Equation (1) implies that any row $\mathbf{r}_i$ of Mat $(\mathbf{y} + \mathbf{x}\mathcal{G})$ is in the row space of $\mathcal{C}$ and therefore all the maximal minors of the matrix $\binom{\mathbf{r}_i}{\mathcal{C}}$ are equal to 0. Also, it is straightforward to check that row $\mathbf{r}_i$ in Mat $(\mathbf{y} + \mathbf{x}\mathcal{G})$ is a vector whose components are affine linear forms in the $x_{i,j}$'s which are the entries of Mat $(\mathbf{x})$. By performing Laplace expansion of any such maximal minor with respect to the first row, this minor can be written as a bilinear polynomial in the $x_{i,j}$'s on the one hand and the maximal minors $c_T$ of $\mathcal{C}$ on the other hand. This gives a bilinear system SM-$\mathbb{F}_q$, which as explained above, is not specific to the RD problem: we obtain a similar system for generic MinRank whose $x_i$ variables (coefficients in the rank $\le r$ linear combination) play the role of our $x_{i,j}$'s. Following the terminology of [17], we call these $x_{i,j}$ variables *linear variables* and the $c_T$'s the *minor variables*.

**Modeling 3 (SM-$\mathbb{F}_q$)** Applied to an RD instance, the SM Modeling from [17] is the system

$$ \left\{ Q_{i,I} := \left| \binom{\mathbf{r}_i}{\mathcal{C}} \right|_{*,I} : I \subset \{1..n\}, \#I = r+1, i \in \{1..m\}, \mathbf{r}_i = \text{Mat}(\mathbf{y} + \mathbf{x}\mathcal{G})_{i,*} \right\} \quad (\text{SM-$\mathbb{F}_q$}) $$
**Unknowns:** $\binom{n}{r}$ variables $c_T$ searched over $\mathbb{F}_q$, $k \cdot m$ variables $x_{j,j'}$ searched over $\mathbb{F}_q$, $j \in \{1..m\}$, $j' \in \{1..k\}$,

**Equations:** $m\binom{n}{r+1}$ equations $Q_{i,I} = 0$ which are affine bilinear polynomials over $\mathbb{F}_q$ in the $x_{j,j'}$'s and in the $c_T$'s.

If there are more linearly independent equations than bilinear monomials, the system may be solved by linearization (i.e. by replacing the monomials by single variables and then obtaining the values of these variables from solving the resulting linear system). Otherwise, the authors propose a dedicated technique to solve at higher degree by multiplying the SM-$\mathbb{F}_q$ equations by monomials of degree $b-1$ in the linear variables to obtain equations of degree $b$ in the linear variables and degree 1 in the $c_T$'s. This amounts to constructing the bi-degree $(b, 1)$ Macaulay matrix $M_b(\text{SM-}\mathbb{F}_q)$ whose columns are indexed by the $M_b$ bi-degree $(b, 1)$ monomials and then to finding a non-trivial element in the right kernel of this matrix. This approach works if the rank of $M_b(\text{SM-}\mathbb{F}_q)$ is $|M_b| - 1$, so that the solution space is one-dimensional and allows to recover the original solution to the MinRank problem. The complexity of the attack is then dominated by the one of solving the system at bi-degree $(b, 1)$, and for this it can be beneficial to use the Wiedemann algorithm as the Macaulay matrix is sparse enough for large values of $b$.

**Solving RD by combining MaxMinors and Support-Minors.** Recall that in the particular RD case we obtained two algebraic systems involving the same $c_T$ variables, namely the MaxMinors system $\text{MM-}\mathbb{F}_q$ and the Support-Minors system $\text{SM-}\mathbb{F}_q$. This suggests to combine both modelings by multiplying the MaxMinors equations by degree $b$ monomials in the linear variables and the Support-Minors equations by degree $b-1$ monomials in the linear variables to get equations of bi-degree $(b, 1)$. In [17], it was implicitly assumed that the MaxMinors and the Support-Minors systems behave independently at higher degree, namely $\text{rk}(M_b(\text{SMM-}\mathbb{F}_q)) = \text{rk}(M_b(\text{MM-}\mathbb{F}_q)) + \text{rk}(M_b(\text{SM-}\mathbb{F}_q))$ when this number is smaller than $M_b$ which is the number of bi-degree $(b, 1)$ monomials. Here $M_b(\text{MM-}\mathbb{F}_q)$ and $M_b(\text{SMM-}\mathbb{F}_q)$ respectively denote the Macaulay matrices of the MaxMinors system multiplied by the monomials of degree $b$ in the linear variables and the vertical join of $M_b(\text{MM-}\mathbb{F}_q)$ and $M_b(\text{SM-}\mathbb{F}_q)$. While it is trivial to estimate $\text{rk}(M_b(\text{MM-}\mathbb{F}_q))$ as the MaxMinors equations $\text{MM-}\mathbb{F}_q$ are linear in the other block of variables, note that the value obtained in [17] for $\text{rk}(M_b(\text{SM-}\mathbb{F}_q))$ is based on much more involved combinatorial arguments and remains conjectural.

**Contributions.** Most of our work concerns the aforementioned combined approach on the Rank Decoding Problem but some of our results will also apply to the Support-Minors strategy of [17] on non-structured MinRank instances.

First, in this combined RD approach, we show that the implicitly assumed relation $\text{rk}(M_b(\text{SMM-}\mathbb{F}_q)) = \text{rk}(M_b(\text{MM-}\mathbb{F}_q)) + \text{rk}(M_b(\text{SM-}\mathbb{F}_q))$ does not hold. Indeed, there are linear dependencies between the two systems: in particular, we
will prove that the MaxMinors equations and some multiples are included in the vector space generated by the Support-Minors equations. We will prove this by considering the "$\mathbb{F}_{q^m}$-version" of both systems. For MaxMinors, this is nothing but the original MaxMinors system MM-$\mathbb{F}_{q^m}$ with coefficients over $\mathbb{F}_{q^m}$. For the $\mathbb{F}_{q^m}$-Support-Minors modeling, this $\mathbb{F}_{q^m}$-version comes from a slight variation of the argument used in [17] for obtaining the Support-Minors modeling. Instead of considering the matrix version of

$$ \mathbf{y} + \mathbf{x}\mathbf{G} = (s_1, \dots, s_r)\mathbf{C}, \qquad (2) $$

we can directly use this equation to argue that the vector $\mathbf{y} + \mathbf{x}\mathbf{G}$ is in the row space of $\mathbf{C}$, which in turn implies that all the maximal minors of the matrix $(\mathbf{y}+\mathbf{x}\mathbf{G})$ are equal to 0. By performing Laplace expansion of these minors according to the first row, we obtain in this way $(\begin{smallmatrix} n \\ r+1 \end{smallmatrix})$ equations which are bilinear in the entries $x_i$ of $\mathbf{x}$ (we still call them the linear variables) and in the maximal minors $c_T$ of $\mathbf{C}$:

### Modeling 4 (SM-$\mathbb{F}_{q^m}$)

$$ \left\{ Q_I := \left| \begin{pmatrix} \mathbf{x}\mathbf{G} + \mathbf{y} \\ \mathbf{C} \end{pmatrix} \right|_{*,I} : I \subset \{1..n\}, \#I = r+1 \right\} \quad (\text{SM-$\mathbb{F}_{q^m}$}) $$

**Unknowns:** $(\begin{smallmatrix} n \\ r \end{smallmatrix})$ variables $c_T$ searched over $\mathbb{F}_q$, k variables $x_1, \dots, x_k$ searched over $\mathbb{F}_{q^m}$,

**Equations:** $(\begin{smallmatrix} n \\ r+1 \end{smallmatrix})$ equations $Q_I = 0$ for $I \subset \{1..n\}$, $\#I = r+1$, viewed as affine bilinear equations over $\mathbb{F}_{q^m}$ in the $x_i$'s on the one hand and in the $c_T$'s on the other hand.

This SM-$\mathbb{F}_{q^m}$ system presents the advantage of being much more compact than the original Support-Minors modeling: the number of linear variables is divided by $m$ (but the unknowns are now in $\mathbb{F}_{q^m}$) and the number of equations is also divided by $m$. Also, this reduced system will be very handy to study the aforementioned linear dependencies, see Section 3:

(i) it is readily seen that the Support-Minors equations are the result of the Unfold operation applied to these SM-$\mathbb{F}_{q^m}$ equations;

(ii) it is easier to exhibit linear dependencies between the equations in MM-$\mathbb{F}_{q^m}$ and SM-$\mathbb{F}_{q^m}$, which in turn yield linear dependencies between the MaxMinors and the Support-Minors equations over $\mathbb{F}_q$.

This is not the only advantage in considering SM-$\mathbb{F}_{q^m}$ instead of the original Support-Minors equations. It will namely be easier to understand the linear dependencies in the SM-$\mathbb{F}_{q^m}$ equations themselves (which also exist as we will show). Moreover, the very fact that the number of linear variables has shrunk a great deal suggests that instead of using the linearization strategy followed in [17], it might be much more favorable to
(i) use the linear equations linking the minor variables $c_T$ from unfolding MM-$\mathbb{F}_{q^m}$ (the MM-$\mathbb{F}_q$ linear system) equations to substitute for some of them in SM-$\mathbb{F}_{q^m}$ and decrease the number of minor variables in it to obtain a new bilinear system SM-$\mathbb{F}_{q^m}^+$;

(ii) multiply these equations by monomials of degree $b-1$ in the linear variables $x_i$ to obtain a new bi-degree $(b, 1)$ system with a reduced number of bi-degree $(b, 1)$ monomials and choose $b$ large enough so that the linearizing strategy is able to recover the values of these bi-degree $(b, 1)$ monomials.

We call this the “attack over $\mathbb{F}_{q^m}$” and we describe it in Section 4, together with the count of the number of equations.

### Modeling 5 (SM-$\mathbb{F}_{q^m}^+$ over $\mathbb{F}_{q^m}$)

$$ \mathrm{SM}-\mathbb{F}_{q^m}^{+} := \mathrm{SM}-\mathbb{F}_{q^m} \mod (\mathrm{MM}-\mathbb{F}_q) \quad (\mathrm{SM}-\mathbb{F}_{q^m}^{+}) $$

**Unknowns:** $\binom{n}{r} - m\binom{n-k-1}{r}$ variables $c_T$ searched over $\mathbb{F}_q$, and $k$ unknowns $x_1, \dots, x_k$ searched over $\mathbb{F}_{q^m}$,

**Equations:** $\binom{n}{r+1} - \binom{n-k-1}{r+1} - (k+1)\binom{n-k-1}{r}$ equations of the form $\tilde{Q}_I = 0$ with $I \subset \{1..n\}$, $\#I = r+1$, $\#(I \cap \{1..k+1\} \ge 2)$, where $\tilde{Q}_I = Q_I \mod (\mathrm{MM}-\mathbb{F}_q)$ is the $Q_I$ equation with $c_T$ variables removed using MM-$\mathbb{F}_q$.

Second, we show how this “attack over $\mathbb{F}_{q^m}$” and more generally any Support-Minors based MinRank attack may benefit from a hybrid approach similar to the one presented in [17, §4.3] on MaxMinors. There, it was used to decrease the number of minor variables. However, we will show that in our case where we consider systems with minor and linear variables, this hybrid technique has the additional benefit of decreasing the number of linear variables. Roughly speaking, our approach is to associate to a given instance of MinRank (resp. RD) $q^{a \cdot r}$ new MinRank instances (resp. RD instances) with smaller parameters for which we know that one of them has its rank $r$ matrix $M$ equal to zero on a fixed set of $a \ge 0$ columns. On any of these instances and by starting from the initial modeling, we hope to find a solution of this particular form by (i) writing that $\binom{n}{r} - \binom{n-a}{r}$ minors $c_T$ should be equal to 0, namely all those that involve one of these $a$ columns (ii) writing $a \cdot m$ linear relations between the linear variables which correspond to the $a \cdot m$ zero entries of $M$. All in all, we may attack a MinRank problem of parameters $(m, n, K, r)$ by performing $q^{a \cdot r}$ attacks on smaller instances with parameters $(m, n - a, K - a \cdot m, r)$ and such that only one of them has a solution. This is much more efficient than the straightforward hybrid approach suggested in [17, §5.5] which consists in fixing a few linear variables and which results only at best in a marginal gain in the complexity. Here, the gain in complexity is much more significant as shown in Subsection 6.1. On a deeper level, our approach also allows to interpolate between the former combinatorial attacks [42] and the algebraic attacks (in particular the plain Support-Minors attack).
## 2 Notation and preliminaries

Vectors are denoted by lower case boldface letters such as $x$, $e$ and matrices by upper case letters $G$, $M$. The all-zero vector of length $\ell$ is denoted by $0_{\ell}$. The $j$-th coordinate of a vector $x$ is denoted by $x_j$ and the submatrix of a matrix $M$ formed from the rows in $I$ and columns in $J$ is denoted by $M_{I,J}$. When $I$ (resp. $J$) consists of all the rows (resp. columns), we may use the notation $M_{*,J}$ (resp. $M_{I,*}$). Similarly, we simplify $M_{i,*} = M_{\{i\},*}$ (resp. $M_{*,j} = M_{*,\{j\}}$) for the $i$-th row of $M$ (resp. $j$-th column of $M$) and $M_{i,j} = M_{\{i\},\{j\}}$ for the entry in row $i$ and column $j$. Finally, $|M|$ is the determinant of a matrix $M$, $|M|_{I,J}$ is the determinant of the submatrix $M_{I,J}$ and $|M|_{*,J}$ the one of $M_{*,J}$.

We will intensively use the Cauchy-Binet formula that expresses the determinant of the product of two matrices $A \in \mathbb{K}^{r \times n}$ and $B \in \mathbb{K}^{n \times r}$ as

$$|AB| = \sum_{T \subset \{1..n\}, \#T=r} |A|_{*,T} |B|_{T,*} \quad (3)$$

The notation $\{1..n\}$ stands for the set of integers from 1 to $n$, and for any subset $J \subset \{k+1..n\}$, we denote by $J-k$ the set $J-k = \{j-k : j \in J\} \subset \{1..n-k\}$.

For $q$ a prime power and $m \ge 1$ an integer, let $\mathbb{F}_q$ be the finite field with $q$ elements and let $\mathbb{F}_{q^m}$ be the extension of $\mathbb{F}_q$ of degree $m$. For $x \in \mathbb{F}_{q^m}$ and $0 \le \ell \le m-1$, we write $x^{[\ell]} := x^{q^\ell}$ for the $\ell$-th Frobenius iterate of $x$, and this notation is extended to matrices component by component, namely $M^{[\ell]} := (M_{i,j}^{[\ell]})_{i,j}$. We also make use of the trace operator which is the $\mathbb{F}_q$-linear mapping from $\mathbb{F}_{q^m}$ to $\mathbb{F}_q$ defined by

$$\mathrm{Tr}(x) := x + x^q + \cdots + x^{q^{m-1}} = \sum_{\ell=0}^{m-1} x^{[\ell]}.$$

In the whole paper, we consider a fixed basis $\beta := (\beta_1, \dots, \beta_m)$ of $\mathbb{F}_{q^m}$ over $\mathbb{F}_q$. The dual basis $\beta^* := (\beta_1^*, \dots, \beta_m^*)$ of $\beta$ is defined by

$$\mathrm{Tr}(\beta_i \beta_j^*) = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{otherwise.} \end{cases}$$

Note that for any decomposition in $\beta$ of the form $x = \sum_{i=1}^m x_i \beta_i \in \mathbb{F}_{q^m}$ and any $i \in \{1..m\}$, we can recover

$$\mathrm{Tr}(\beta_i^* x) = x_i. \quad (4)$$

For a vector $x = (x_1, \dots, x_n) \in \mathbb{F}_{q^m}$ we denote by $\mathrm{Tr}(x)$ the vector $(\mathrm{Tr}(x_i))_{1 \le i \le n}$ where the trace is applied componentwise, and for any matrix $M \in \mathbb{F}_{q^m}^{b \times c}$ we denote by $\mathrm{Tr}(M) = (\mathrm{Tr}(M_{i,j}))_{i,j}$. It will be helpful to notice that, thanks to the linearity of $\mathrm{Tr}$ over $\mathbb{F}_q$,

$$\mathrm{Tr}(\beta_i^* x) = \mathrm{Mat}(x)_{i,*} \quad \forall i \in \{1..m\}, \quad (5)$$

$$\mathrm{Tr}(CM) = C \mathrm{Tr}(M) \quad \text{if } C \in \mathbb{F}_q^{a \times b}, M \in \mathbb{F}_{q^m}^{b \times c}. \quad (6)$$
When looking for solutions of a polynomial system in $\mathbb{F}_q$ with coefficients in $\mathbb{F}_{q^m}$, it will be helpful to notice that for $f(\boldsymbol{z}) \in \mathbb{F}_{q^m}[z_1, \dots, z_N]$ and $\boldsymbol{x} = (x_1, \dots, x_N) \in \mathbb{F}_q^N$, we have:

$$f(x_1, \dots, x_N) = 0 \iff \forall i \in \{1..m\}, \operatorname{Tr}(\beta_i^* f(\boldsymbol{x})) = 0. \quad (7)$$

This motivates to define the “unfolding” operation which associates to an algebraic system $\mathcal{F} := \{f_1, \dots, f_M\} \subset \mathbb{F}_{q^m}[z_1, \dots, z_N]$ with coefficients in $\mathbb{F}_{q^m}$ an equivalent algebraic system over $\mathbb{F}_q$ which defines the same variety over $\mathbb{F}_q$. We call it the associated unfolded system:

$$\text{Unfold}(\{f_1, \dots, f_M\}) := \{\operatorname{Tr}(\beta_i^* f_j) \mod I_q : 1 \le i \le m, 1 \le j \le M\} \in \mathbb{F}_q[\boldsymbol{z}]^{M \cdot m}, \quad (8)$$

where we reduce the polynomials modulo the field equations, i.e. $I_q := \langle z_1^q - z_1, \dots, z_N^q - z_N \rangle$. For one single polynomial $f(\boldsymbol{z}) = \sum_{\alpha \in \mathbb{N}^N} a_\alpha \boldsymbol{z}^\alpha \in \mathbb{F}_{q^m}[\boldsymbol{z}]$, this reduction process reads

$$\operatorname{Tr}(\beta_i^* f(\boldsymbol{z})) \mod I_q = \sum_{\alpha \in \mathbb{N}^N} \operatorname{Tr}(\beta_i^* a_\alpha) \boldsymbol{z}^\alpha \in \mathbb{F}_q[\boldsymbol{z}]. \quad (9)$$

In other words, this results in applying the function $x \mapsto \operatorname{Tr}(\beta_i^* x)$ to each coefficient of the polynomial.

It is clear that the solutions to $\mathcal{F}$ in $\mathbb{F}_q^N$ are exactly the solutions to Unfold($\mathcal{F}$) in $\mathbb{F}_q^N$ and that any solution to Unfold($\mathcal{F}$) in any extension field of $\mathbb{F}_q$ is a solution to $\mathcal{F}$. However, note that it may be the case that $\mathcal{F}$ has more solutions than Unfold($\mathcal{F}$) in some extension field.<fnref n="6" />

We refer to [31] for basics on polynomial systems and Gröbner basis computation. For the different results in the paper, we consider a particular monomial ordering on our two sets of variables $x_1, \dots, x_k$ and $c_T$'s for any subset $T$ of size $r$. The $c_T$'s are ordered with a reverse lexicographical order according to $T$: $c_{T'} > c_T$ if $t'_j = t_j$ for $j < j_0$ and $t'_{j_0} > t_{j_0}$ where $T = \{t_1 < \dots < t_r\}$ and $T' = \{t'_1 < \dots < t'_r\}$. We then choose a grevlex (graded reverse lexicographical) monomial ordering $x_1 > \dots > x_k > c_T$. Finally, we denote by $\text{LT}(f)$ the leading term of a polynomial $f$ with respect to this term order, and $\text{NF}(f, \mathcal{G})$ the normal form of a polynomial $f$ with respect to a system $\mathcal{G}$.

### 3 MaxMinors and Support-Minors systems for RD instances

In this section, we analyse the two RD modelings over $\mathbb{F}_{q^m}$ which take advantage of the underlying extension field structure, namely the MaxMinors (MM-$\mathbb{F}_{q^m}$) and the Support-Minors (SM-$\mathbb{F}_{q^m}$) systems.

<footnote n="6">⁶ For instance in $\mathbb{F}_{q^2}$, $f = \beta_1 z_1 + \beta_2 z_2$ admits all multiples of $(\beta_2/\beta_1, 1)$ as solution, whereas Unfold($f$) = $\{z_1, z_2\}$ admits only $(0, 0)$ as a solution in the algebraic closure of $\mathbb{F}_{q^2}$.</footnote>
The (MM-\mathbb{F}_{q^m}) system was already described in [16,17] and recalled in the introduction. The particular form of the MM-\mathbb{F}_{q^m} polynomials $P_J$ as linear polynomials comes from the fact that these $P_J$'s can be expressed in terms of the maximal minors of $C$ by using the Cauchy-Binet formula (3). Actually, we also use implicitly the Plücker coordinates associated to the vector space generated by the rows of $C$ by defining new variables $c_T = |C|_{*,T}$, see [25, p.6]. For $N = \binom{n}{r} - 1$ and $\mathbb{P}^N(\mathbb{F}_q) = \mathbb{P}(\mathbb{F}_q^{N+1})$ the projective space, the Plücker map is defined by

$$p: \{W \subset \mathbb{F}_q^n : \dim(W) = r\} \to \mathbb{P}^N(\mathbb{F}_q) \\ C \mapsto (c_T)_{T \subset \{1..n\}, \#T=r}$$

where $C$ is any matrix whose rows generate the vector space $W$. The map is well defined: any other generating matrix of $W$ can be written $AC$ for some invertible matrix $A \in GL(r, \mathbb{F}_q)$, and the image $p(AC) = \det(A)(c_T)_T$ is the same projective point as $(c_T)_T$. Moreover, the map is injective, and given the values of all maximal minors of a matrix it is easy to reconstruct an equivalent matrix (up to the multiplication by an invertible $A$) that has the same values for the minors (see [25, p.7] for instance).

In our algebraic system, introducing such coordinates brings the benefit of reducing the number of solutions: for a given RD solution, there are several solutions $C \in \mathbb{F}_q^{r \times n}$ to the initial equation (2) but there are unique Plücker coordinates. As already pointed out in [17], it is also extremely beneficial for the computation to replace polynomials $|C|_{*,T}$ with $r!$ terms of degree $r$ in the entries of $C$ by single variables $c_T$'s in $\mathbb{F}_q$. Our second set of polynomials, namely the (SM-\mathbb{F}_{q^m}) system, was also described in the introduction. The particular bi-linear shape of these polynomials in the linear and in the minor variables follows by applying Laplace expansion along the first row $xG + y$ of $(xG+y)_C$. Recall also that these minor variables $c_T$ are searched over $\mathbb{F}_q$ while the linear variables $x_j$ are searched over $\mathbb{F}_{q^m}$. In particular, as the MM-\mathbb{F}_{q^m} polynomials are over $\mathbb{F}_{q^m}$ but linear in these $c_T$ variables, it is possible to generate $m$ times more linear polynomials in the same variables by forming the unfolded system MM-\mathbb{F}_q = Unfold(MM-\mathbb{F}_{q^m}) as already explained in Section 2. While these MM-\mathbb{F}_{q^m} polynomials are proven to be linearly independent in [17], it is only conjectured that the resulting MM-\mathbb{F}_q polynomials are linearly independent with overwhelming probability.

In Section 3.1, we show that the two systems over $\mathbb{F}_{q^m}$ described above are not independent: the MM-\mathbb{F}_{q^m} polynomials are actually included in SM-\mathbb{F}_{q^m}; thus, adding the MM-\mathbb{F}_q polynomials to the SM-\mathbb{F}_q system does not help to solve RD in the underdetermined case as stated in [17]. Also, SM-\mathbb{F}_{q^m} is an interesting modeling in itself to attack the RD problem as it consists of more compact polynomials over the extension field $\mathbb{F}_{q^m}$. Moreover, we are able to formally prove the linear independence of these polynomials and more generally the exact dimension of the vector space generated by them at each bi-degree $(b, 1)$ for any $b \ge 1$, which is clearly the key quantity to evaluate the cost of such an attack.
However, we show that it is not possible to solve the system by using only these polynomials over $\mathbb{F}_{q^m}$, even at high bi-degree $(b, 1)$. Finally, note that it is also possible to unfold the SM-$\mathbb{F}_{q^m}$ polynomials over $\mathbb{F}_q$ but at the cost of multiplying the number of linear variables by a factor $m$ as we also need to express each $x_j = \sum_{i=1}^m x_{i,j}\beta_i$ in $\mathbb{F}_{q^m}$ as $m$ times more variables over $\mathbb{F}_q$. In Section 3.2, we show that the result of this operation is nothing more than the system (SM-$\mathbb{F}_q$) which is the Support Minors Modeling of [17] applied to an RD instance, namely SM-$\mathbb{F}_q = \text{Unfold}(\text{SM-}\mathbb{F}_{q^m})$. In Proposition 5, we also give a proof for the number of linearly independent polynomials in SM-$\mathbb{F}_q$ that are not in MM-$\mathbb{F}_q$ and which can be seen as the extra information brought by Support-Minors.

For the sake of clarity, most of the proofs are postponed in Appendix A.

## 3.1 MaxMinors and Support-Minors modelings over $\mathbb{F}_{q^m}$.

In what follows, we always consider RD instances with a unique solution and whose rank weight is exactly $r$ instead of at most $r$ (we may assume this, as trying all the weights smaller than $r$ adds at most a polynomial factor in the total complexity). Let $\mathcal{G} \in \mathbb{F}_{q^m}^{k \times n}$ be a full-rank generator matrix of a linear code $\mathcal{C}$ of length $n$ and dimension $k$ over $\mathbb{F}_{q^m}$, and let $\mathbf{y} \in \mathbb{F}_{q^m}^n$ be the received word affected by an error of weight $r$. With our assumption, the decoding problem amounts to finding the unique codeword $\mathbf{x}\mathcal{G}$ such that the weight of $\mathbf{x}\mathcal{G} + \mathbf{y}$ is $r$.

In this section, we analyze the link between the MM-$\mathbb{F}_{q^m}$ modeling (1), consisting of polynomials $P_J = |CH_y^T|_{*,J}$, and the SM-$\mathbb{F}_{q^m}$ modeling (4), consisting of polynomials $Q_I = |(\mathbf{x}\mathcal{G}+\mathbf{y})|_{*,I}$. To this end, we first separate the polynomials from both systems into different sets by defining for nonnegative integers $s$ and $i \in \{1..k\}$:

$$ 
\begin{aligned}
Q_s &= \{Q_I : I \subset \{1..n\}, \ #I = r+1, \ # (I \cap \{1..k+1\}) = s\}, \\
Q_{\ge s} &= \{Q_I : I \subset \{1..n\}, \ #I = r+1, \ # (I \cap \{1..k+1\}) \ge s\}, \\
P &= \{P_J : J \subset \{1..n-k-1\}, \ #J = r\}, \\
x_i P &:= \{x_i P : P \in \mathcal{P}\}.
\end{aligned}
$$

We are going to prove the following relations, where $\langle \cdot \rangle_{\mathbb{F}_q}$ means the vector space generated over $\mathbb{F}_q$:

$$ 
\begin{aligned}
& Q_0 \subset \langle Q_1, Q_{\ge 2} \rangle_{\mathbb{F}_q} \quad (\text{Proposition 1}) \\
& \langle \mathcal{P}, x_i \mathcal{P} : i \in \{1..k\}, Q_{\ge 2} \rangle_{\mathbb{F}_q} = \langle Q_1, Q_{\ge 2} \rangle_{\mathbb{F}_q} \quad (\text{Proposition 3}) \\
& \mathcal{P}, x_i \mathcal{P} : i \in \{1..k\}, Q_{\ge 2} \text{ are linearly independent over } \mathbb{F}_q \quad (\text{Proposition 2})
\end{aligned}
$$
The consequence is that if we linearize the (affine) SM-$\mathbb{F}_{q^m}$ system, we get several reductions to zero and also $\binom{n-k-1}{r}$ degree falls<fnref n="7" /> that give the $P_J$'s polynomials. If we then eliminate $c_T$ variables using those linear polynomials, we get new reductions to zero which correspond to the $x_i P_J$'s. More generally, Proposition 4 tackles the augmented bi-degree $(b, 1)$ case by giving the number of linearly independent $Q_I$ polynomials for any $b \ge 1$ and without any particular assumption. For all these propositions, it will be helpful to notice that

**Fact 1** The RD problem is equivalent to a problem where the code $\mathcal{C}$ has a generator matrix $\mathbf{G}$ in systematic form, i.e. $\mathbf{G} = (\mathbf{I}_k *)$, where $\mathbf{y} = (\mathbf{0}_k 1 *)$ and where the extended code $\mathcal{C} + \langle \mathbf{y} \rangle$ has a parity-check matrix $\mathbf{H}_{\mathbf{y}}$ in systematic form, i.e., $\mathbf{H}_{\mathbf{y}} = (* \mathbf{I}_{n-k-1})$. Then, $\mathbf{H} := (\mathbf{H}_{\mathbf{y}})$ is a parity-check matrix for $\mathcal{C}$ for a vector $\mathbf{h} = (* 1 \mathbf{0}_{n-k-1})$ lying in the dual $\mathcal{C}^{\perp}$. We have $\mathbf{y}\mathbf{h}^{\top} = 1$.

*Proof.* Up to a permutation of the coordinates, we can assume that $\mathbf{G}$ is in systematic form $\mathbf{G} = (\mathbf{I}_k *)$, and up to the addition of an element in $\mathcal{C}$ that $\mathbf{y} = (\mathbf{0}_k *)$. As $\mathbf{y}$ contains an error of weight $r$, it is non-zero, so that up to a permutation of the coordinates of the code and up to the multiplication by a constant in $\mathbb{F}_{q^m}$, we assume that $\mathbf{y}$ has the given shape $\mathbf{y} = (\mathbf{0}_k 1 *)$. Now, if $\tilde{\mathbf{G}}_{\mathbf{y}} = (\mathbf{I}_{k+1} \mathbf{A})$ is a generator matrix of $\mathcal{C}_{\mathbf{y}}$ in systematic form, then $\mathbf{H}_{\mathbf{y}} := (-\mathbf{A}^{\top} \mathbf{I}_{n-k-1})$ is suitable. By considering an $\mathbf{h}$ linearly independent from the rows of $\mathbf{H}_{\mathbf{y}}$ and such that $\mathbf{y}\mathbf{h}^{\top} \neq 0$, any linear combination between $\mathbf{h}$ and the rows of $\mathbf{H}_{\mathbf{y}}$ still satisfies the same properties. Therefore, we may assume that $\mathbf{h} = (* \mathbf{0}_{n-k-1})$, and moreover we have $\mathbf{y}\mathbf{h}^{\top} = h_{k+1} \neq 0$. Thus, the vector $h_{k+1}^{-1}\mathbf{h}$ is indeed of the form (* 1 $\mathbf{0}_{n-k-1}$). □

**Proposition 1.** The polynomials in $Q_0$ can be obtained as linear combinations between the polynomials in $Q_{\ge 1}$:

$$Q_{T+k+1} = - \sum_{Q_I \in Q_{\ge 1}} |\mathbf{H}_{\mathbf{y}}|_{T,I} Q_I, \quad \forall T \subset \{1..n-k-1\}, \ #T = r+1. \quad (10)$$

*Proof.* This comes from the relations $\left| \begin{pmatrix} \mathbf{x}\mathbf{G} + \mathbf{y} \\ \mathbf{C} \end{pmatrix} \mathbf{H}_{\mathbf{y}}^{\top} \right|_{*,T} = 0$, see Appendix A.1 for details. □

**Proposition 2.** The polynomials in $\mathcal{P} \cup Q_{\ge 2}$ are linearly independent, as

$$\mathrm{LT}(P_J) = c_{J+k+1} \qquad (P_J \in \mathcal{P})$$

$$\mathrm{LT}(Q_I) = x_{i_1} c_{I \setminus \{i_1\}} \qquad (Q_I \in Q_{\ge 2}, i_1 = \min(I))$$

Moreover, each variable $c_{J+k+1}$ for any $J \subset \{1..n-k-1\}$, $\#J = r$ appears only as the leading term of $P_J$ and does not appear in any of the polynomials in $Q_{\ge 2}$ nor in $P_{J'}$ with $J' \neq J$.

<footnote n="7">⁷ for affine systems, degree falls correspond to linear combinations between polynomials of a given degree that yield nonzero polynomials of smaller degree.</footnote>
Proof. See Appendix A.2. □

**Proposition 3.** The polynomials in $Q_1$ generate the same $\mathbb{F}_{q^m}$-vector space as the polynomials

$$ \mathcal{P} \cup \bigcup_{j=1}^{k} x_j \mathcal{P} $$

modulo the polynomials in $Q_{\ge 2}$. More precisely, for any $J \subset \{1..n-k-1\}$, $\#J = r$ and $j \in \{1..k\}$ we have

$$ \begin{aligned} P_J &= Q_{\{k+1\} \cup (J+k+1)} + \sum_{Q_I \in Q_{\ge 2}} (-1)^r |\mathbf{H}|_{J \cup \{n-k\}, I} Q_I \\ x_j P_J &= Q_{\{j\} \cup (J+k+1)} + \sum_{Q_I \in Q_{\ge 2}, j \in I} (-1)^{1+\mathrm{Pos}(j,I)} |\mathbf{H}_{y}|_{J,I \setminus \{j\}} Q_I \end{aligned} $$

where $\mathrm{Pos}(i_u, I) = u$ for $I = \{i_1, \dots, i_{r+1}\}$ such that $i_1 < \dots < i_{r+1}$.

Proof. This comes from the relations $P_J = (-1)^r \left| \begin{pmatrix} \mathbf{xG} + \mathbf{y} \\ \mathbf{C} \end{pmatrix} \begin{pmatrix} \mathbf{Hy} \\ \mathbf{h} \end{pmatrix}^\mathrm{T} \right|_{*,J \cup \{n-k\}}$ and $x_j P_J = (-1)^r \left| \begin{pmatrix} \mathbf{xG} + \mathbf{y} \\ \mathbf{C} \end{pmatrix} \begin{pmatrix} \mathbf{Hy} \\ e_j \end{pmatrix}^\mathrm{T} \right|_{*,J \cup \{n-k\}}$ with $e_j$ the $j$-th canonical basis vector in $\mathbb{F}_q^n$, see Appendix A.2 for details. □

To conclude this section, we have shown that the polynomials $P_J$ and $Q_{\ge 2}$ are linearly independent and that the polynomials in $Q_0$ and $Q_1$ are redundant to the system. Moreover, each polynomial $P_J$ can be used to eliminate the variable $c_{J+k+1}$ from the system, so that solving $\mathcal{P} \cup Q_{\ge 2}$ amounts to solve $Q_{\ge 2}$, that does not contain the variables $c_{J+k+1}$. Similarly to [17], a natural approach is now to linearize at higher bi-degree $(b, 1)$ after multiplying the polynomials by linear variables. Here, we are able to describe precisely the $\mathbb{F}_{q^m}$-vector space generated by the polynomials $Q_{\ge 2}$ augmented at bi-degree $(b, 1)$ (see Appendix A.3 for the proof). The basis is constructed from $Q_{\ge 2}$ without any computation:

**Proposition 4.** For any $b \ge 1$, the $\mathbb{F}_{q^m}$-vector space generated by the polynomials $Q_{\ge 2}$ augmented at bi-degree $(b, 1)$ by multiplying by monomials of degree $b-1$ in the $x_i$ variables admits the following basis:

$$ \mathcal{B}_b = \left\{ x_{i_1}^{\alpha_{i_1}} \dots x_k^{\alpha_k} Q_I : \begin{array}{l} I = \{i_1 < i_2 < \dots < i_{r+1}\}, \\ i_2 \le k+1, \sum_{j \ge i_1} \alpha_j = b-1 \end{array} \right\} \quad (11) $$

In particular, it has dimension

$$ \mathcal{N}_b^{\mathbb{F}_{q^m}} := \sum_{i=1}^{k} \binom{n-i}{r} \binom{k+b-1-i}{b-1} - \binom{n-k-1}{r} \binom{k+b-1}{b}, \quad (12) $$
and there are

$$ \mathcal{M}_b^{\mathbb{F}_{q^m}} := \binom{k+b-1}{b} \left( \binom{n}{r} - \binom{n-k-1}{r} \right) \quad (13) $$

monomials of degree $(b, 1)$. We have $\mathcal{N}_b^{\mathbb{F}_{q^m}} < \mathcal{M}_b^{\mathbb{F}_{q^m}} - 1$ for any $b \ge 1$.

As a consequence, we see that the system $Q_{\ge 2}$ always has more monomials than polynomials and cannot be solved in this way at any degree $b$. The reason is that our initial sets of polynomials are with coefficients in $\mathbb{F}_{q^m}$ and do not take into account the fact that the $c_T$'s are searched in $\mathbb{F}_q$ (the overall system is not zero-dimensional). This will lead us to propose in Section 4 a mixed modeling by using together polynomials over $\mathbb{F}_{q^m}$ and over $\mathbb{F}_q$. Prior to that, we come back to the analysis of these $\mathbb{F}_q$ polynomials in the next section.

## 3.2 MaxMinors and Support-Minors modelings over $\mathbb{F}_q$.

Here we consider the unfolded systems obtained by expressing all polynomials of MM-$\mathbb{F}_{q^m}$ (resp. SM-$\mathbb{F}_{q^m}$) in the fixed basis $\beta := (\beta_1, \dots, \beta_m)$ of $\mathbb{F}_{q^m}$ over $\mathbb{F}_q$ and taking each component, as described in Section 2. For the $P_J$'s, this unfolding process yields by definition the original (MM-$\mathbb{F}_q$) system $\{P_{i,J}\}_{i,J}$ [17] containing $m$ times more polynomials than MM-$\mathbb{F}_{q^m}$ and in the same variables. For the $Q_I$'s, as the linear variables $x_j$ lie in the extension field $\mathbb{F}_{q^m}$, we express each $x_j$ in the basis $\beta$ as $x_j = \sum_{i=1}^m \beta_i x_{i,j}$, yielding $m$ times more linear variables $x_{i,j}$'s. The same unfolding technique is then applied to obtain a system $\{Q_{i,I}\}_{i,I}$, and Proposition 6 will show that it exactly corresponds to the (SM-$\mathbb{F}_q$) system defined in the introduction.

Following previous work (e.g. [16,17]), we assume that the MM-$\mathbb{F}_q$ polynomials $P_{i,J}$ are generically as linearly independent as possible. In other words, if the matrix $\mathbf{H}_y = (\ast I_{n-k-1}) \in \mathbb{F}_{q^m}^{(n-k-1) \times n}$ is obtained from a random code $\mathcal{C}$ of dimension $k$ and length $n$ and from a random vector $\mathbf{e} \in \mathbb{F}_{q^m}^n$ of weight $r$ below the Gilbert-Varshamov distance, we adopt the following assumption:

**Assumption 1** The $m(\binom{n-k-1}{r})$ linear polynomials $P_{i,J}$ in the $\binom{n}{r}$ variables $c_T$ generate an $\mathbb{F}_q$-vector space of dimension $\min(m(\binom{n-k-1}{r}), \binom{n}{r} - 1)$.

To validate this hypothesis, we have also performed experiments. The code used for these simulations can be found in https://github.com/mbardet/Rank-Decoding-tools.

**Remark 2.** If we consider only one $P_J$ polynomial and if we denote by $v_J$ the vector of minors of $(\mathbf{H}_y)_{*,J}$ of size $r$ and by $\mu$ the vector of minors of $\mathcal{C}$ of size $r$, then $P_J = v_J \mu^T$ and the rank of the system $\{P_{i,J} : 1 \le i \le m\}$ is exactly the rank of $v_J$ in rank metric. More generally, the number of linearly independent polynomials in $\{P_{i,J}\}_{i,J}$ is the co-dimension of the subfield subcode of the code generated by the matrix $(v_J)_{J \subset \{1..n-k-1\}, \#J=r}$.
On the contrary, we are able to prove this result for the SM-F<sub>q</sub> polynomials on a specific RD instance. Note that such a statement is not proven for the SM polynomials on a random MinRank instance, so in a way this F<sub>q<sup>m</sup></sub>-linear structure enables one to remove this implicit assumption of [17] in the RD case.

**Proposition 5.** The polynomials in Unfold($Q_{\ge 2}$) satisfy LT($Q_{i,I}$) = $x_{i,i_1}c_{I\setminus\{i_1\}}$ with $i_1 = \min(I) \le k$. In particular, they are all linearly independent over F<sub>q</sub>.

*Proof.* This comes from LT($Q_I$) = $x_{i_1}c_{I\setminus\{i_1\}} = \sum_{i=1}^m \beta_i x_{i,i_1} c_{I\setminus\{i_1\}}$, see Proposition 2.

Finally, we show that the polynomials from SM-F<sub>q</sub> are the unfolded polynomials obtained from SM-F<sub>q<sup>m</sup></sub>. To this end, it may be helpful to give more details about this modeling than those given in the introduction. Let (y, C, r) an RD instance where C is a code of generator matrix G and let

$$ 
\begin{aligned}
\mathcal{M}_0 &:= \mathrm{Mat}(\mathbf{y}) \\
\mathcal{M}_{\ell,j} &:= \mathrm{Mat}(\beta_{\ell} \mathbf{G}_{j,*}) \quad \text{for } \ell \in \{1..m\}, j \in \{1..k\}
\end{aligned}
$$

As observed in [17], this RD problem is equivalent to a MinRank instance with rank r, K = km and matrices

$$ (\mathcal{M}_0, \mathcal{M}_{1,1}, \dots, \mathcal{M}_{i,j}, \dots, \mathcal{M}_{m,k}) \in \mathbb{F}_q^{m \times n}. $$

There, the Support-Minors polynomials are all the maximal minors of the matrices (r<sub>i</sub>/C) for all i ∈ {1..m} and r<sub>i</sub> the i-th row in the solution to the MinRank problem, namely

$$ \mathbf{r}_i = \mathrm{Mat} \left( \mathbf{y} + \sum_{\ell=1}^{m} \sum_{j=1}^{k} x_{\ell,j} \beta_{\ell} \mathbf{G}_{j,*} \right)_{i,*} = \mathrm{Tr}(\beta_i^* (\mathbf{y} + \mathbf{x}\mathbf{G})), $$

where the second equality follows from (5). We have

$$ \mathrm{rk} \left( \mathcal{M}_0 + \sum_{\ell=1}^{m} \sum_{j=1}^{k} x_{\ell,j} \mathcal{M}_{\ell,j} \right) \le r. $$

We then obtain

**Proposition 6.** For any $i \in \{1..m\}$ and any $I \subset \{1..n\}$, $\#I = r + 1$, we have

$$ Q_{i,I} := \left| \begin{pmatrix} \mathbf{r}_i \\ \mathbf{C} \end{pmatrix} \right|_{*,I} = \mathrm{Tr}(\beta_i^* Q_I) \quad \mathrm{mod} \; I_q, $$

where $I_q$ is the ideal generated by all the field equations $x_{\ell,j}^q - x_{\ell,j}$ and $c_T^q - c_T$.
*Proof.* The proposition basically follows from the linearity of the trace and the determinant with respect to its first row and from (9):

$$ \mathrm{Tr} \left( \beta_i^* \left| \begin{pmatrix} \mathbf{y} + \mathbf{x}\mathbf{G} \\ \mathbf{C} \end{pmatrix} \right|_{*,I} \right) \mod I_q = \mathrm{Tr} \left( \left| \begin{pmatrix} \beta_i^* (\mathbf{y} + \mathbf{x}\mathbf{G}) \\ \mathbf{C} \end{pmatrix} \right|_{*,I} \right) \mod I_q \\ = \left| \begin{pmatrix} \mathrm{Tr}(\beta_i^* (\mathbf{y} + \mathbf{x}\mathbf{G})) \\ \mathbf{C} \end{pmatrix} \right|_{*,I} = \left| \begin{pmatrix} \mathbf{r}_i \\ \mathbf{C} \end{pmatrix} \right|_{*,I}. \quad \square $$

# 4 Algebraic approach to solve RD by combining SM-$\mathbb{F}_{q^m}$ and MM-$\mathbb{F}_q$

From the material presented in the previous section, we conclude that the polynomials $P_{i,J}$ over $\mathbb{F}_q$ (i.e. MM-$\mathbb{F}_q$) are necessary to solve the system: without them we cannot solve RD since the previously considered ideal without these polynomials was not zero-dimensional. However, we also noticed that the SM-$\mathbb{F}_q$ polynomials over the small field involve a large number of linear variables compared to SM-$\mathbb{F}_{q^m}$. This leads us to propose a new Modeling 5 to attack RD, which relies on solving SM-$\mathbb{F}_{q^m}$ together with MM-$\mathbb{F}_q$. In this way, we take advantage of all the $m(\binom{n-k-1}{r})$ linear polynomials we can get in the $c_T$'s from MM-$\mathbb{F}_q$ while keeping only $k$ linear variables $x_i$'s over $\mathbb{F}_{q^m}$ from SM-$\mathbb{F}_{q^m}$. This increased compactness makes that even if this system were to be solved at higher degree than SM-$\mathbb{F}_q$, it may perform better from a complexity point of view.

Let $\mathrm{NF}(f, \langle P_{i,J} \rangle)$ be the normal form function that associates to any polynomial $f$ the unique polynomial $\tilde{f} = f \mod \langle P_{i,J} \rangle$ such that no $c_T$ leading term of a polynomial in the $\langle P_{i,J} \rangle$ ideal appears in $\tilde{f}$. Modeling 5 is the system (SM-$\mathbb{F}_{q^m}^+$) over $\mathbb{F}_{q^m}$ which consists of the polynomials in $Q_{\ge 2}$ in which the polynomials $P_{i,J}$'s are used to remove $c_T$ variables, i.e. $\{\tilde{Q}_I, Q_I \in Q_{\ge 2}\}$ where

$$ \tilde{Q}_I := \mathrm{NF}(Q_I, \langle P_{i,J} \rangle). $$

Then, we solve Modeling 5 using the same technique as in [17] by multiplying the polynomials by all possible monomials of degree $b-1$ in the $x_i$'s. Once again, the complexity analysis requires to estimate the dimension of the $\mathbb{F}_{q^m}$-vector space generated by the resulting bi-degree $(b, 1)$ polynomials. According to Proposition 4, there are $\mathcal{N}_b^{\mathbb{F}_{q^m}}$ such polynomials but we provide in this section new syzygies brought by the elimination of the $c_T$ variables using the linear polynomials $P_{i,J}$. We call $\mathcal{N}_{b,syz}^{\mathbb{F}_q}$ the number of those new syzygies, so that the estimated dimension is $\mathcal{N}_b^{\mathbb{F}_{q^m}} - \mathcal{N}_{b,syz}^{\mathbb{F}_q}$. The final cost follows by comparing this number to the number of monomials $\mathcal{M}_b^{\mathbb{F}_q}$.

**Proposition 7.** For any $b \ge 1$, the number of linearly independent polynomials at bi-degree $(b, 1)$ in SM-$\mathbb{F}_{q^m}^+$ is generically

$$ \mathcal{N}_b^{\mathbb{F}_q} = \mathcal{N}_b^{\mathbb{F}_{q^m}} - \mathcal{N}_{b,syz}^{\mathbb{F}_q}, $$
with the exact value (from Proposition 4)

$$ \mathcal{N}_{b}^{\mathbb{F}_{q}^{m}} = \sum_{i=1}^{k} \binom{n-i}{r} \binom{k+b-1-i}{b-1} - \binom{n-k-1}{r} \binom{k+b-1}{b} \quad (28) $$

and the conjectured value, valid as long as $\mathcal{N}_{b}^{\mathbb{F}_{q}} < \mathcal{M}_{b}^{\mathbb{F}_{q}}$:

$$ \mathcal{N}_{b,syz}^{\mathbb{F}_q} = (m-1) \sum_{i=1}^{b} (-1)^{i+1} \binom{k+b-i-1}{b-i} \binom{n-k-1}{r+i}. \quad (14) $$

The number of monomials is

$$ \mathcal{M}_{b}^{\mathbb{F}_{q}} = \binom{k+b-1}{b} \left( \binom{n}{r} - m \binom{n-k-1}{r} \right), \quad (15) $$

so that we can solve $SM-\mathbb{F}_{q}^{+}$ by linearization at bi-degree $(b, 1)$ whenever

$$ \mathcal{N}_{b}^{\mathbb{F}_{q}} \geq \mathcal{M}_{b}^{\mathbb{F}_{q}} - 1. $$

In this case, the final cost in $\mathbb{F}_q$ operations is given by

$$ \mathcal{O}(m^2 \mathcal{N}_{b}^{\mathbb{F}_{q}} \mathcal{M}_{b}^{\mathbb{F}_{q} \omega^{-1}}), $$

where $\omega$ is the linear algebra constant and where the $m^2$ factor comes from expressing each $\mathbb{F}_{q}^{m}$ operation involved in terms of $\mathbb{F}_{q}$ operations.

Note that it is always possible, whenever the ratio between polynomials and variables is much larger than 1, to drop excess polynomials by taking punctured codes much in the same way as in [17, §4.2].

**Analysis of the syzygies in Modeling 5.** Contrary to Section 3, we are not able to give a proof for the number of linearly independent syzygies due to the $P_{i,J}$'s. This comes from the fact that now, for some large enough $b$, we can solve the system, implying that the polynomials are not linearly independent at this degree anymore (hence we cannot give a general proof of independence). Also, we may find specific instances for which our conjecture fails. Still, we can analyse the generic behaviour on random instances. Here, we describe generic syzygies coming from the $\mathbb{F}_{q}^{m}$ structure and we use them to count precisely the number of polynomials and monomials at each bi-degree $(b, 1)$ to determine the success of a solving strategy by linearization in the generic case.

We start by giving a generalization of Proposition 1, that provides an explanation for the relations between the $\tilde{Q}_I$ polynomials starting at bi-degree (1, 1).
**Proposition 8.** For any $T \subset \{1..n-k-1\}$, $\#T = r+1$ and $1 \le i \le m$, we obtain a relation between the $\tilde{Q}_I$ polynomials given by

$$ \mathrm{Tr}(\beta_i^*) \tilde{Q}_{T+k+1} + \sum_{\substack{I \subset \{1..n\} \\ \#I=r+1 \\ I \cap \{k+1..n\} \subseteq T+k+1}} \mathrm{Tr}(\beta_i^* | \mathbf{H}_y|_{T,I}) \tilde{Q}_I = 0. \quad (16) $$

Note that the coefficients of any of these relations belong to $\mathbb{F}_q$.

*Proof.* This comes from the fact that, for any $0 \le \ell \le m-1$:

$$ \Gamma_{\ell,T} := \left| \begin{pmatrix} x\mathbf{G} + \mathbf{y} \\ C \end{pmatrix} (\mathbf{H}_{\mathbf{y}}^{[\ell]})^{\top} \right|_{*,T} = 0 \quad \mathrm{mod} \, \langle P_{i,J} \rangle. $$

Further details as well as the link between $P_J^{[\ell]}$ and $P_{i,J}$ are postponed in Appendix A.4. □

Proposition 8 gives (at most) $m \binom{n-k-1}{r+1}$ syzygies at bi-degree (1, 1) which include the relations from Proposition 1 (the $\ell = 0$ case in the proof).

At degree $b=2$, those relations multiplied by all linear variables generate new relations, but they are not independent anymore: indeed, for $1 \le \ell \le m-1$ and any $T_2 \subset \{1..n-k-1\}$, $\#T_2 = r+2$ the following minor gives $(m-1) \binom{n-k-1}{r+2}$ relations between the $\mathcal{N}_{1,syz}^{\mathbb{F}_q}$ syzygies at bi-degree (1, 1):

$$ \left| \begin{pmatrix} x\mathbf{G} + \mathbf{y} \\ x\mathbf{G} + \mathbf{y} \\ C \end{pmatrix} (\mathbf{H}_{\mathbf{y}}^{[\ell]})^{\top} \right|_{*,T_2} = 0, $$

More generally, a similar inclusion-exclusion combinatorial argument as those used to derive [17, Heuristic 2] leads to the following Conjecture 1, that was verified experimentally for $b=2$, $b=3$ and $b=4$.

*Conjecture 1.* For $b \ge 1$, the number of independent syzygies is expected to be equal to

$$ \mathcal{N}_{b,syz}^{\mathbb{F}_q} = (m-1) \sum_{i=1}^{b} (-1)^{i+1} \binom{k+b-i-1}{b-i} \binom{n-k-1}{r+i}. $$

# 5 Hybrid technique on minor variables

In algebraic cryptanalysis, “hybrid approach” usually refers to a generic method to possibly decrease the complexity of an algebraic attack by (a) choosing a subset of unknowns, (b) specializing them to some value, (c) solving the new system with less unknowns and (d) finally trying all possible specializations of those unknowns. The point is that in certain cases, the complexity gain in solving the new system supersedes the loss in complexity coming from exhaustive search.
In [17], an indirect approach is followed on the MaxMinors modeling. Instead of performing a naive exhaustive search on random minor variables, the authors proceed by fixing $a \ge 0$ columns in $\mathcal{C}$. It can readily be seen that this provides $N := \binom{n}{r} - \binom{n-a}{r}$ linear polynomials involving the $c_T$'s. These polynomials can in turn be used to reduce the number of $c_T$ variables by the same amount and this costs only to test $q^{a \cdot r}$ different choices instead of trying $q^N$ choices if we had performed the naive exhaustive search on $N$ variables.

We show here that a variation of this idea, namely if we can fix $a$ columns of $\mathcal{C}$ to 0, or basically what amounts to the same, if we can fix to 0 $a$ positions of the error $e$ we seek in the RD problem, can have a dramatic effect on the Support-Minors modeling. Not only do we have the aforementioned reduction in the $c_T$ variables, but we do have a reduction of the number of linear variables as well. Moreover, the effect of this hybrid approach is even independent from the algebraic modeling or algorithm we use to solve the MinRank/RD problem in the sense that this hybrid approach actually provides a reduction to a smaller MinRank/RD problem. More precisely (we give here the explanation just for the RD problem):

1. If by chance $a$ positions of the error vector are zero and the $a$ positions belong to an information set of the code, it is possible to reduce the problem with parameters $(m, n, k, r)$ to a smaller instance with parameters $(m, n - a, k - a, r)$;

2. This has a chance $\frac{1}{q^{ar}}$ to happen for a random instance;

3. It is possible to change the initial instance into an instance satisfying Point 1, either by using a deterministic search among all $q^{ar}$ possible transformations, or by using a rerandomizing trick that will succeed with probability $O(q^{-ar})$.

The idea to look for a particular error with zero positions is used in [38, §5.2], where the rerandomizing trick is implicit (see the proof of Proposition 3 there). Here, we present a way to reduce the solving of an RD instance to a smaller problem when the error vector is zero on some positions. The advantage is that the method is applicable to any algorithm solving RD.

As explained above, this is more general and it actually applies to any MinRank problem. The rerandomizing trick applies equally to both cases and we begin our discussion by explaining it. The proofs are somewhat simpler in the RD case and we start with this more specific case before turning to the MinRank case. We end the section with a probabilistic description of the rerandomization trick.

## 5.1 Rerandomizing the MinRank and the RD instances

There is no reason a priori why $a$ positions of the RD solution $e$ or $a$ columns of the MinRank solution $\mathcal{E} = \mathcal{M}_0 + \sum_{i=1}^K \mathcal{M}_i$ would be equal to 0. The point is that we can multiply on the right $e$ or $\mathcal{E}$ by an invertible $n \times n$ matrix $\mathbf{P}$ with coefficients over $\mathbb{F}_q$. This does not change the rank weight of $e$ or the rank of $\mathcal{E}$, but now $a$ positions or $e$ or $a$ columns of $\mathcal{E}$ have a chance to be equal to 0.
Moreover, if we make the following assumption on the $(m, n, k, r)$-RD instance $(\mathbf{y}, \mathcal{C}, r)$ or the $(m, n, K, r)$ MinRank instance $(\mathbf{M}_0, \mathbf{M}_1, \dots, \mathbf{M}_K, r)$,

**Assumption 2** In the RD case, we assume that the first $r$ positions of the solution $\mathbf{e}$ are independent over $\mathbb{F}_q$. In the MinRank case, we assume that the first $r$ columns of the solution $\mathbf{E} = \mathbf{M}_0 + \sum_{i=1}^K x_i \mathbf{M}_i$ are independent.

then we can even try at most $q^{ar}$ matrices belonging to the set

$$ \mathcal{P} := \left\{ \mathbf{P}_A = \begin{pmatrix} \mathbf{I}_r & \mathbf{0}_{r \times (n-a-r)} & -\mathbf{A} \\ \mathbf{0}_{(n-a-r) \times r} & \mathbf{I}_{n-a-r} & \mathbf{0}_{(n-a-r) \times a} \\ \mathbf{0}_{a \times r} & \mathbf{0}_{a \times (n-a-r)} & \mathbf{I}_a \end{pmatrix}, \mathbf{A} \in \mathbb{F}_q^{r \times a} \right\}. \quad (17) $$

The point is that multiplying by matrices of this form amounts to leave the $(n-a)$ columns in the first two blocks unchanged, but adds to the last $a$ positions of $\mathbf{e}$ or the last $a$ columns of $\mathbf{E}$ all possible linear combinations of the $r$ first ones. One of them has to be 0 because by assumption, the $r$ first positions/columns form a basis of the subspace $\langle e_1, \dots, e_n \rangle_{\mathbb{F}_q}$ or the column space of $\mathbf{E}$. One could think that this would give a new instance of the MinRank problem associated to the matrices $\mathbf{M}'_0 = \mathbf{M}_0 \mathbf{P}_A$, $\mathbf{M}'_1 = \mathbf{M}_1 \mathbf{P}_A$, ..., $\mathbf{M}'_K = \mathbf{M}_K \mathbf{P}_A$, or an RD problem associated to the word $\mathbf{y}' = \mathbf{y} \mathbf{P}_A$ and the code $\mathcal{C}_A = \{c \mathbf{P}_A : c \in \mathcal{C}\}$, however the fact that the last columns are equal to 0 has an additional effect, we can namely reduce accordingly the dimension of the matrix code (in the rank metric case) or of the underlying $\mathbb{F}_{q^m}$-linear code. Let us verify this in the RD case first. We are going now to use the following notation in the subsections that follow

$$ J := \{n - a + 1..n\} \quad (18) $$

$$ \check{J} := \{1..n - a\}. \quad (19) $$

## 5.2 RD instances

It turns out that in RD case, when $(e\mathbf{P}_A)_J = \mathbf{0}_a$, with a very mild condition on the shortened code at $J$ we obtain a reduction to an RD instance with smaller parameters, namely

**Proposition 9.** Assume that $e_J = \mathbf{0}$. Let $\mathbf{Sh}_J(C)$ be the code $\mathcal{C}$ shortened at $J$, namely $\mathbf{Sh}_J(C) = \{c_j : c \in \mathcal{C}, c_j = \mathbf{0}\}$. Assume that $\mathbf{Sh}_J(C)$ is of dimension $k-a$, then by Gaussian elimination on a generator matrix $\mathbf{G}$ of $\mathcal{C}$ we can obtain a generator matrix of $\mathcal{C}$ in systematic form on the columns in $J$, i.e.

$$ DG = \begin{pmatrix} \check{J} & J \\ \mathbf{G}' & \mathbf{0}_{(k-a) \times a} \\ \mathbf{B} & \mathbf{I}_a \end{pmatrix} $$

for some invertible matrix $\mathbf{D} \in \mathbb{F}_{q^m}^{k \times k}$. Then $\mathbf{G}'$ is a generator matrix of $\mathcal{C}' := \mathbf{Sh}_J(C)$. Define $\mathbf{y}' := (\mathbf{y})_{\check{J}} - \mathbf{y}_{J}\mathbf{B}$. Then $(\mathbf{y}', \mathcal{C}', r)$ is a valid instance of an RD problem of parameters $(m, n - a, k - a, r)$, from which we can deduce a solution of the initial problem $(\mathbf{y}, \mathcal{C}, r)$.
Proof. The first point is just standard linear algebra. For the second point, let $(c, e = y - c)$ be the solution of the RD problem and denote by $(x', x'')$ where $x' \in \mathbb{F}_q^{k-a}$ and $x'' \in \mathbb{F}_q^a$ the vector defined by

$$ (x', x'') = xD^{-1} \quad \text{where} \\ c = xG. $$

Observe now that

$$ \begin{aligned} e_J &= y_J - c_J \\ &= y_J - (xG)_J \\ &= y_J - ((x', x'')DG)_J \\ &= y_J - x''. \end{aligned} $$

Since $e_J = 0_a$, this implies $y_J = x''$. Therefore

$$ \begin{aligned} e_j &= y_j - c_j = y_j - x'G' - x''B \\ &= \underbrace{y_j - y_jB}_{y'} - \underbrace{x'G'}_{=c' \in C'} \\ &= c' \in C' \end{aligned} $$

Therefore $y' - c'$ is of rank weight $r$ and the proposition follows. $\square$

<figure><img src="image_2.png" /></figure>

This proposition is used as follows. When we want to solve an instance $(y, C, r)$ of an RD problem of parameters $(m, n, k, r)$, we consider $q^{ar}$ RD instances $(y', C', r)$ of parameters $(m, n - a, k - a, r)$ obtained from all $P_A \in \mathcal{P}$ by computing a generator matrix $G_A := GA$ (where $G$ is a generator matrix of $C$) of the code $C_A := \{cP_A : c \in C\}$, then put this matrix in (partial) systematic form on the columns in $J$ by Gaussian elimination and obtain

$$ G'' = \begin{pmatrix} J & J \\ G' & 0_{(k-a) \times a} \\ B & I_a \end{pmatrix}. \qquad (20) $$

The RD instances $(y', C', r)$ are defined from $G'$, $y$ and $P_A$ by

$$ C' := \{xG' : x \in \mathbb{F}_{q^m}^{k-a}\} $$

$$ y' := y''_J - y''_J B, \text{ where} $$

$$ y'' := y P_A. $$

Finally, one of these instances has a solution from which we recover the solution of the original problem thanks to Proposition 9.

It remains to check under which condition we can put $G_A$ in partial systematic form for any $A \in \mathbb{F}_q^{r \times a}$ as required in (20). This is given by Proposition 9: namely that $Sh_J(C_A)$ should have dimension $k - a$ for any $A$. There are two cases to consider:

**Case 1:** $a + r \le k$.

In this case, there is a very mild condition on $C$ for which the relevant property holds for any $A \in \mathbb{F}_q^{r \times a}$, namely that
**Lemma 1.** Provided that there exists a systematic set for $\mathcal{C}$ that contains $\{1, \dots, r\} \cup J$, the code $\mathrm{Sh}_J(\mathcal{C}_A)$ has dimension exactly $k-a$ for all $\mathbf{A} \in \mathbb{F}_q^{r \times a}$.

*Proof.* By reordering the positions we may assume that the systematic set is $\{1..k\}$ and $J = \{r+1..r+a\}$ and

$$ P_A = \begin{pmatrix} I_r & -A & 0_{r \times (n-a-r)} \\ 0_{a \times r} & I_a & 0_{a \times (n-a-r)} \\ 0_{(n-a-r) \times r} & 0_{(n-a-r) \times a} & I_{n-a-r} \end{pmatrix}. $$

On the other hand we can assume by the hypothesis of the lemma that we can choose the generator matrix of $\mathcal{C}$ as

$$ G = (I_k R). $$

The generator matrix of $\mathcal{C}_A$ is of the form

$$ GP_A = \begin{pmatrix} I_r & -A & 0_{r \times (n-a-r)} & R_1 \\ 0_{a \times r} & I_a & 0_{a \times (k-a-r)} & R_2 \\ 0_{(k-a-r) \times r} & 0_{(k-a-r) \times a} & I_{k-a-r} & R_3 \end{pmatrix}. $$

This code $\mathcal{C}_A$ is therefore still systematic in the first $k$ positions and hence $\mathrm{Sh}_J(\mathcal{C}_A)$ has dimension exactly $k-a$. $\square$

**Case 2:** $r+a > k$.

Note that in this case, the $\mathbb{F}_{q^m}$-linear code $\mathcal{D}$ of parameters $[r+a, k]$ which is generated by the matrix $G_{*,\{1..r\}} \cup J \in \mathbb{F}_{q^m}^{k \times (r+a)}$ is not the full code. It is also worthwhile to notice that $\mathrm{Sh}_J(\mathcal{C}_A)$ has dimension $k-a$ if and only if the matrix $G_{*,J} - G_{*,\{1..r\}}A$ has rank $a$. To verify whether or not this property holds for any $\mathbf{A}$ we use the following lemma.

**Lemma 2.** The existence of a matrix $\mathbf{A} \in \mathbb{F}_q^{r \times a}$ such that $G_{*,J} - G_{*,\{1..r\}}A$ is rank defective is equivalent to the existence of a word of weight $\le a$ whose support is spanned by the last coordinates in the dual of $\mathcal{D}$.

*Proof.* Assume that some $\mathbf{A} \in \mathbb{F}_q^{r \times a}$ is such that $\mathrm{rk}(G_{*,J} - G_{*,\{1..r\}}A) < a$. This means that there exists a vector $\lambda_A \in \mathbb{F}_{q^m}^a$ such that

$$ -G_{*,\{1..r\}}A\lambda_A^\top + G_{*,J}\lambda_A^\top = G_{*,\{1..r\}} \cup J \underbrace{\left(\begin{array}{c} -A\lambda_A^\top \\ \lambda_A^\top \end{array}\right)}_{:=v_A^\top} = 0. $$

In particular, the vector $v_A \in \mathbb{F}_{q^m}^{a+r}$ belongs to $\mathcal{D}^\perp$, its weight is $\le a$ (as the entries of $\mathbf{A}$ belong to $\mathbb{F}_q$) and its support is spanned by the last coordinates. The converse statement is similar by constructing an inverse of the map $\mathbf{A} \mapsto v_A$.

$\square$

Under the assumption that $\mathcal{D}$ behaves as a random code with parameters $[a+r, k]$, one can show that
**Proposition 10.** The probability that there exists in the dual of a random $\mathbb{F}_{q^m}$-linear code of parameters $[a+r, k]$ a non zero codeword of weight $\le a$ whose support is spanned by the last coordinates is upper-bounded by $\Theta(q^{(m+r)a-mk})$ as $q \to \infty$.

*Proof.* This probability is upper-bounded by the probability that there exists simply a non zero codeword of weight $\le a$ in such a code. Let $X$ be the number of such codewords. We use the fact that $\mathrm{Pr}(X \ne 0) \le \mathbb{E}(X)$ and that the expected number $\mathbb{E}(X)$ of non-zero vectors of weight $\le a$ in such a code is given by

$$ \mathbb{E}(X) = \frac{B_a - 1}{q^{mk}}, $$

where $B_a$ is the size of a ball of radius $a$ in $\mathbb{F}_{q^m}^{a+r}$ in the rank metric. By using [46, Proposition 1] the size of such a ball is of the form $\Theta(q^{(m+a+r)a-a^2}) = \Theta(q^{(m+r)a})$ for any nonnegative integer $a \le m$. We deduce the proposition from this. $\square$

## 5.3 MinRank instances

This reduction sketched for the RD problem also applies to MinRank. Consider a MinRank instance $(M_0, \dots, M_K)$ with target rank $r$, and denote by $E = M_0 + \sum_{i=1}^K x_i M_i$ the rank $r$ matrix we are looking for. To explain the form taken by the reduced RD instances we got in Subsection 5.2, it was convenient to put the generator matrix of the transformed code $C_A = CP_A$ into systematic form. It will be helpful here to use a similar notion in the MinRank case by viewing a matrix as the vector formed by the concatenation of its rows. To define the relevant systematic form we will use, we bring in the invertible linear map

$$ \begin{align} \varphi : \mathbb{F}_q^{m \times n} &\to \mathbb{F}_q^{mn} \tag{21} \\ \mathbf{A} &\mapsto (\mathbf{A}_{i,j})_{i \in \{1..m\}, j \in \{1..n\}} \nonumber \end{align} $$

where the image of $\varphi(\mathbf{A})$ is formed by the entries of $\mathbf{A}$ in column-major order (we could equivalently take the row-major order). Using $\varphi$ we define the generator matrix associated to a MinRank instance as follows.

**Definition 1.** Let $M_1, \dots, M_K$ be $K$ matrices in $\mathbb{F}_q^{m \times n}$, and define $\mathcal{L}$ the matrix code generated by the $\varphi(M_i)$'s. Then the following matrix $\mathbf{L}$ is a $K \times mn$ generator matrix of $\mathcal{L}$:

$$ \mathbf{L}(M_1, \dots, M_K) := \begin{pmatrix} \varphi(M_1) \\ \vdots \\ \varphi(M_K) \end{pmatrix} \in \mathbb{F}_q^{K \times mn}. $$
As noted in [19, §4.4], any elementary row operation on $L$ corresponds to linear transformations of the variables $x_i$, i.e. we can always transform the initial MinRank instance to an equivalent one with $L$ in echelon form. From now on, we will assume that $L$ is in echelon form.

**Definition 2.** We say that MinRank instance is in systematic form if its associated generator matrix is. We denote by $S$ the systematic positions.

It is clear that

**Fact 2** If the MinRank instance is in systematic form, we can equivalently reduce $\varphi(\mathbf{M}_0)$ w.r.t. the generator matrix, then it has $K$ zeros in positions belonging to $S$. In this case, $\varphi(\sum_{i=0}^K x_i \mathbf{M}_i)$ contains $K$ consecutive positions equal to $(x_i)_{i \in S}$, i.e. the $K$ entries of the matrix $\mathbf{E}$ belonging to $S$ are exactly the $K$ corresponding linear variables.

**Remark 3.** It is not always possible to put a MinRank instance in systematic form, as not any permutation of columns in $\mathbb{F}_q^{nm}$ preserves the rank (the permutation needs to permute blocks of columns in the corresponding matrix). But as noted in [19], a random MinRank instance will be in systematic form with high probability.

We use the same notation as in (18) and (19) for $J$ and $\tilde{J}$ and denote by $I$ the set of positions of $\{1..mn\}$ that correspond to the columns indexed by the positions in $J$, that is $I = \cup_{j \in J} \{(j-1)m + 1..jm\}$. Following the approach in [38, Prop. 3], we first analyze the complexity of solving the MinRank instance with the columns in $J$ specialized to zero. We will then see how we can reduce to this case, by using either a deterministic, or a probabilistic approach.

**Proposition 11 (Assuming the error is zero on coordinates in J).** Consider a MinRank instance $(\mathbf{M}_0, \dots, \mathbf{M}_K)$ in $\mathbb{F}_q^{m \times n}$ with target rank $r$. Assume that $am \le K$ and that the solution $\mathbf{x}$ satisfies $\mathbf{E}_{*,J} = \mathbf{0}_{m \times a}$, or equivalently $\varphi(\mathbf{M}_0)_I + \mathbf{x}\mathbf{L}_{*,I} = \mathbf{0}_{am}$. Let $\mathcal{L}' := \text{Sh}_I(\mathcal{L})$ be the code $\mathcal{L}$ shortened at $I$. Assume that $\text{Sh}_I(\mathcal{L})$ is of dimension $K-am$, then a solution $\mathbf{x}$ for $(\mathbf{M}_0, \dots, \mathbf{M}_K)$ with target rank $r$ can be deduced from the solution of a smaller MinRank instance $(\mathbf{M}'_0, \dots, \mathbf{M}'_{K-am})$ in $\mathbb{F}_q^{m \times (n-a)}$ with target rank $r$.

More precisely, by Gaussian elimination on $L$ we can obtain a generator matrix of $\mathcal{L}$ in systematic form on the columns in $I$, i.e. after permuting positions, so that the last positions belong to $I$:

$$DL = \begin{pmatrix} L' & \mathbf{0}_{(K-am) \times am} \\ B & I_{am} \end{pmatrix}$$

for some invertible matrix $D \in \mathbb{F}_q^{K \times K}$. Then $L' \in \mathbb{F}_q^{(K-am) \times m(n-a)}$ is a generator matrix of $\mathcal{L}'$. Define $\mathbf{M}'_i$ to be the $m \times (n-a)$ matrix corresponding to the $i$-th row in $L'$, and $\mathbf{M}'_0 = \varphi^{-1}(\varphi(\mathbf{M}_0)\tilde{I} - \varphi(\mathbf{M}_0)IB)$ of size $m \times (n-a)$,

<footnote n="8">⁸ We abusively use the same name $\varphi: \mathbb{F}_q^{m \times n} \to \mathbb{F}_q^{mn}$ and $\mathbb{F}_q^{m \times (n-a)} \to \mathbb{F}_q^{m(n-a)}$.</footnote>
where $\tilde{I} := \{1..mn\} \setminus I$. Then $M'_0, M'_1, \dots, M'_{K-am} \in \mathbb{F}_q^{m \times (n-a)}$ is a MinRank instance with target rank $r$, and any solution $x'$ of this instance gives a solution $x = D(x' x'')$ of the initial instance with $x'' = -\varphi(M_0)_I$.

*Proof.* To simplify the explanations, we assume that the positions in $\{1..mn\}$ have been permuted, so that the last $am$ positions belong to $I$. By hypothesis, we have $DL_{*,I} = \begin{pmatrix} 0 \\ I_{am} \end{pmatrix}$, so that if $xD^{-1} = (x' x'')$ with $x'$ of size $K-am$, the hypothesis $\varphi(M_0)_I + xL_{*,I} = 0$ is equivalent to $x'' + \varphi(M_0)_I = 0$. As $E_J = 0$, the matrix $E_J$ has rank $r$, and is given by

$$ \begin{aligned} \varphi(E_J) &= \varphi(E)_I = x' L' + x'' B + \varphi(M_0)_{\tilde{I}} \\ &= x' L' - \varphi(M_0)_I B + \varphi(M_0)_{\tilde{I}}. \end{aligned} $$ 
 i.e. $E_J = M'_0 + \sum_{i=1}^{K-am} x'_i M'_i$.

We get the smaller MinRank instance described in the proposition. $\square$

<figure><img src="image_3.png" /></figure>

A deterministic way to reduce to the zero case. Similarly to the RD case, we can reduce a MinRank problem of parameters $(m, n, K, r)$ to solving $q^{ar}$ MinRank instances of parameters $(m, n - a, K - am, r)$ obtained by multiplying the $M_i$'s by $P_A$ in $\mathcal{P}$, then under the assumption that all shortened codes are of rank $K-am$ we can apply Proposition 11 to them. Eventually, exactly one of the resulting $(M_0 P_A, \dots, M_K P_A)$ instances will have a solution that is zero on the columns $J$, and then leads to the desired solution. We give here an example where it is always true provided that $(r + a)m \le K$.

**Lemma 3.** Assume the MinRank instance is in systematic form on a set of positions $S$ that contains $\{1..rm\} \cup I$, then $\text{Sh}_I(L_A)$ has rank $K-am$ for all $A \in \mathbb{F}_q^{r \times a}$.

*Proof.* The matrices $M_i^A := M_i P_A$ are identical to $M_i$ on the columns $\tilde{J}$, and the columns in $J$ are $(M_i^A)_{*,J} = (M_i)_{*,J} - (M_i)_{*,\{1..r\}} A$. We reorder the positions so that the systematic positions are the $K$ first ones and such that $I = \{rm + 1..(r+a)m\}$. If the MinRank instance is in systematic form then for $i \in \{1..K\}$ such that $i = (v-1)m + u$ with $v \in \{1..n\}$ and $u \in \{1..m\}$, we have that $(M_i)_{*,\{1..r+a\}}$ has at most only one nonzero entry 1 in position $(u,v)$ if $v \le r+a$, and is all zero otherwise. This means that

$$ (M_i)_{*,\{1..r\}} = 0_{m \times r} \quad \text{hence} \quad M_i^A = M_i \quad \text{for } i \ge rm + 1, $$

and that

$$ (M_i^A)_{*,J} = \begin{pmatrix} 0 \\ -A_{v,*} \\ 0 \end{pmatrix} \leftarrow \text{row } u \quad \text{for } i \in \{1..rm\}. $$
Finally, this means that

$$ L_A = \begin{pmatrix} \text{positions in } I & & & \\ I_{rm} & \begin{pmatrix} \text{coefficients} \\ \text{depending} \\ \text{on } \mathbf{A} \end{pmatrix} & 0 & L_{\{1..rm\}, \{(a+r)m+1..nm\}} \\ 0 & I_{am} & 0 & L_{\{rm+1..(r+a)m\}, \{(a+r)m+1..nm\}} \\ 0 & 0 & I_{K-(a+r)m} & L_{\{(r+a)m+1..K\}, \{(a+r)m+1..nm\}} \end{pmatrix} $$

is full rank on the columns in $I = \{rm + 1..(r+a)m\}$, i.e. that $\text{Sh}_I(L_A)$ has rank $K-am$. $\square$

## 5.4 Probabilistic hybrid approach on MinRank or RD instances

The approach given in the previous sections is a deterministic way to solve generic MinRank or RD instances. However, it does not work if the initial conditions on the solution $E$ of the MinRank problem or on the solution $e$ of the RD problem are not met, i.e. the first $r$ columns of $E$ are not linearly independent, or the first $r$ entries of $e$ are not linearly independent over $\mathbb{F}_q$. This can be fixed by considering instead a randomized algorithm, which consists in multiplying on the right the MinRank instance by a random $n \times n$ invertible matrix $P$ over $\mathbb{F}_q$ which gives with probability $\Omega(1)$ a new instance of the $(m, n, K, r)$ MinRank problem which satisfies all the right assumptions and on which we can apply the aforementioned technique. Once we have solved the new MinRank problem, we recover the solution of the original MinRank by multiplying it on the right by $P^{-1}$. A similar technique can also be used for the RD problem. This might even be improved slightly by multiplying on the right each time by a new $P$ and making directly the bet that $EP$ has all its $a$ columns in $J$ equal to 0 (i.e we assume directly that we have an instance of the $(m, n-a, K-am, r)$ problem). This has a probability of $\Omega(q^{-ar})$ to happen. In both cases, we get a probabilistic algorithm of similar complexity as the deterministic algorithm, with the difference that it would work on any $(m, n, K, r)$ instance of the MinRank problem.

## 5.5 Complexity of the hybrid technique

Let $\mathcal{A}$ be an algorithm that solves the MinRank problem, and $T_{\mathcal{A},\text{plain},(m,n,K,r)}$ its cost on a generic MinRank problem of parameters $(m, n, K, r)$. In the MaxMinters case, the original purpose of fixing columns in $\mathcal{C}$ was to end up with an overdefined linear system. Here, fixing $a \ge 0$ columns yields to the solving of a smaller problem. Therefore, the cost of the hybrid technique is estimated by solving a minimization problem over $a \ge 0$. Under the assumption that the resulting MinRank instances of parameters $(m, n-a, K-am, r)$ behave as random, we have

**Proposition 12.** The time complexity of the proposed hybrid technique on a generic MinRank problem of parameters $(m, n, K, r)$ is given by

$$ T_{\mathcal{A},\text{hybrid},(m,n,K,r)} = \min_{a \ge 0} (q^{ar} \cdot T_{\mathcal{A},\text{plain},(m,n-a,K-am,r)}). $$
We may obtain a similar statement in the RD case, where we consider any algorithm A to solve RD.

**Proposition 13.** The time complexity of the proposed hybrid technique applied to an algebraic algorithm A to solve an RD problem of parameters (m, n, k, r) is given by

$$T_{A,hybrid,(m,n,k,r)} = \min_{a \ge 0} (q^{ar} \cdot T_{A,plain,(m,n-a,k-a,r)}).$$

In particular, this applies to the new SM-$\mathbb{F}_{q^m}^+$ approach presented in this paper. The overall complexity may be easily computed by combining Proposition 7 to obtain $T_{SM-\mathbb{F}_{q^m}^+, plain}$ with Proposition 12.

# 6 Estimated costs on MinRank and RD instances.

Finally, we provide the bit complexity of the attacks described in this paper on some parameter sets. First, we apply the hybrid technique described in Section 5 to the Support-Minors modeling on generic MinRank instances (see Proposition 12). The same technique is then used on the SM-$\mathbb{F}_{q^m}^+$ system from Section 4 to attack RD instances (see Proposition 7 and Proposition 13). In both cases, these attacks are compared to former attacks on MinRank and RD. The magma code used to produce the Tables and Figures is available on https://github.com/mbardet/Rank-Decoding-tools.

## 6.1 MinRank instances

On the plain MinRank problem, the approach of Section 5 on Support-Minors allows to reach smaller complexities than the ones obtained with the specialization technique of [17] which consists in fixing linear variables. More interestingly, our proposed hybrid approach actually offers a trade-off between combinatorial attacks (e.g. Goubin's Kernel attack [42]) and pure algebraic attacks. Indeed, the bet that we make can be seen as guessing $a \ge 0$ vectors in the right kernel of the low rank matrix $M$ similar to [42], the difference being that we consider less vectors than $\lceil \frac{K}{m} \rceil$.

As an illustration, we give the complexity of our attack on the parameters of the MinRank based signature scheme [20] in Table 1 which builds upon the seminal work of Courtois [29]. Note that the parameters proposed in [20] already take into account our improved MinRank attack.

## 6.2 RD instances

Recall that the cost of the best combinatorial attack of [13] in $\mathbb{F}_q$ operations is

$$O\left((n-k)^{\omega} m^{\omega} q^{r \lceil \frac{(k+1)m}{n} \rceil - m}\right), \qquad (22)$$

where $\omega$ is the linear algebra constant. It is now common to take $\omega = 2$: this value is optimistic, but take into account any algorithm that could take advantage
<table><caption>**Table 1.** Bit complexity of the Kernel attack and the hybrid SM attack on the parameters from [20]. The number of guessed vectors in the Kernel attack is equal to $a := \lceil \frac{K}{n} \rceil$ and the final complexity in $\mathbb{F}_q$-operations is $O(q^{a \cdot r} K^\omega)$. For the SM attack, we report the triplet $(b, a, n_{\text{cols}})$ which leads to the best complexity: “a” refers to the number of guessed columns, “$n_{\text{cols}}$” is the number of columns in the reduced MinRank problem ($\le n-a$) and $b$ is the degree at which we solve via SM. Finally, we adopt $\omega = 2$ as in [20], a constant factor of 7 in Strassen’s algorithm and we consider that a multiplication over $\mathbb{F}_{2^4}$ represents 23 binary operations. We also report in this table the optimized kernel attack as given in [20] which improves on the polynomial factor in front of the complexity.</caption><thead><tr><th>(q, m, n, K, r)</th><th>λ</th><th>Kernel (a)</th><th>Kernel in [19] (a)</th><th>SM Section 5 (b, a, n<sub>cols</sub>)</th></tr></thead><tbody><tr><td>(16, 16, 16, 142, 4)</td><td>128</td><td>166 (9)</td><td>158 (8)</td><td>161 (5, 6, n - a)</td></tr><tr><td>(16, 19, 19, 167, 6)</td><td>192</td><td>238 (9)</td><td>231 (8)</td><td>231 (7, 6, n - a)</td></tr><tr><td>(16, 22, 22, 254, 6)</td><td>256</td><td>311 (12)</td><td>303 (11)</td><td>297 (1, 11, n - a)</td></tr></tbody></table>

of the structure of the matrices. Also, cryptographically relevant RD instances are such that $r = O(\sqrt{n})$ or such that the weight $r$ is closer to the Gilbert-Varshamov bound, and we selected parameter sets corresponding to these two situations. The $r = O(\sqrt{n})$ regime is for instance the one encountered in the NIST submissions ROLLO and RQC. In Table 2, we give the binary logarithm of the complexity of our attack “over $\mathbb{F}_{q^m}$” on ROLLO-I parameters and we also keep track of the optimum values of $a$ and $b$. This cost is compared to the one of the combinatorial attack of [13] (“comb”) and to the one of the MaxMinors attack (“MM.”).

<table><caption>**Table 2.** Comparison between known attacks on the new ROLLO-I parameters in [17] and [3] after the 2021-04-21 update. The “*”-symbol means that the best attack is obtained on the derived code from key attack with parameters $(m, n, k, r) = (m, 2k - \lfloor \frac{k}{d} \rfloor, k - \lfloor \frac{k}{d} \rfloor, d)$, where $d$ refers to the rank of the moderate weight codewords in the masked LRPC code. Otherwise, the attack is on an RD problem with parameters $(m, 2k, k, r)$. The struck out numbers are the underestimated values from [17, Table 3]. We also adopt $\omega = 2$, whereas previous values where computed with $\omega = 2.81$.</caption><thead><tr><th>Instance</th><th>q</th><th>k</th><th>m</th><th>r</th><th>d</th><th>MM-F<sub>q</sub></th><th>a</th><th>p</th><th>SM-F<sup>+</sup><sub>q<sub>m</sub></sub></th><th>b</th><th>a</th><th>comb</th></tr></thead><tbody><tr><td>new2ROLLO-I-128</td><td>2</td><td>83</td><td>73</td><td>7</td><td>8</td><td>205</td><td>18</td><td>0</td><td>180 202</td><td>2</td><td>13</td><td>212</td></tr><tr><td>new2ROLLO-I-192</td><td>2</td><td>97</td><td>89</td><td>8</td><td>8</td><td>226*</td><td>17</td><td>0</td><td>197* 223*</td><td>1</td><td>14</td><td>282*</td></tr><tr><td>new2ROLLO-I-256</td><td>2</td><td>113</td><td>103</td><td>9</td><td>9</td><td>371*</td><td>30</td><td>1</td><td>283* 366*</td><td>1</td><td>27</td><td>375*</td></tr><tr><td>ROLLO-I-128-spe</td><td>2</td><td>83</td><td>67</td><td>7</td><td>8</td><td>212</td><td>19</td><td>0</td><td>214</td><td>2</td><td>15</td><td>196</td></tr><tr><td>ROLLO-I-192-spe</td><td>2</td><td>97</td><td>79</td><td>8</td><td>8</td><td>242*</td><td>19</td><td>0</td><td>241*</td><td>2</td><td>15</td><td>251*</td></tr><tr><td>ROLLO-I-256-spe</td><td>2</td><td>113</td><td>97</td><td>9</td><td>9</td><td>380*</td><td>31</td><td>0</td><td>376*</td><td>2</td><td>27</td><td>353*</td></tr></tbody></table>

Figs. 1 and 2 contain a broader comparison between the same attacks for fixed $(m, n, k) = (31, 33, 15)$ and weight $r$ between 2 and $d_{\text{RGV}} = 10$, for $q = 2$ in Fig. 1 and $q = 256$ in Fig. 2. We can see that for $q = 2$, the algebraic attacks become
less efficient than combinatorial attacks for large $r$. This justifies the current trend for rank-based proposals to now consider a different regime where the weight $r$ is chosen closer to the rank Gilbert-Varshamow bound $d_{\text{RGV}} = O(n)$, see for instance [5,24]. Note also that in the scheme of [5] which uses LRPC codes, choosing $d$ of the same order as $r$ somehow increases the rank of the moderate weight codewords in the masked LRPC code and therefore may allow to gain confidence in the indistinguishability assumption. This behavior can be explained by the fact that for the combinatorial attacks, the exponential part of the complexity all depends on $q$, whereas for the MM-$\mathbb{F}_q$ attack, the cost $q^{ar} \binom{n-a}{r}^{\omega}$ contains a part depending on $q$ whereas the other part $\binom{n-a}{r}^{\omega}$ does not depend on $q$. This is the same for SM-$\mathbb{F}_{q^m}^+$.

<figure><img src="image_4.png" /><figcaption>**Fig. 1.** Comparison between the theoretical $\log_2$ complexities $C$ of MM-$\mathbb{F}_q$/SM-$\mathbb{F}_{q^m}^+$ (the best one, hybrid and punctured version) and of the combinatorial attack for RD instances with fixed $(m, n, k) = (31, 33, 15)$ and various values of $r$. The rank Gilbert-Varshamow bound is $d_{\text{RGV}}(m, n, k, q = 2) = 10$.</figcaption></figure>

We illustrate in Fig. 2 the fact that our approach over $\mathbb{F}_{q^m}$ becomes interesting compared to MM-$\mathbb{F}_q$ as $q$ increases, and for small values of $r$. This can be explained by the fact that SM-$\mathbb{F}_{q^m}^+$ contains two blocks of variables, the $c_T$'s and the $x_i$'s, and introducing the $x_i$'s variables has a computational cost that make MM-$\mathbb{F}_q$ competitive for large $r$. For large $q$, the cost of the hybrid approach becomes higher and the SM-$\mathbb{F}_{q^m}^+$ approach more competitive, as it can solve with a smaller $a$ at a larger $b$. We plot in Fig. 3 the optimal values of $a$ and compare the MM-$\mathbb{F}_q$ approach with SM-$\mathbb{F}_{q^m}^+$ for $q = 2$ and $q = 2^8$.

**General picture of the complexities of generic RD instances.** Even if it is difficult to draw general conclusions for the complexity of the different attacks against the Rank Decoding problem, our simulations seem to show that
<figure><img src="image_5.png" /><figcaption>**Fig. 2.** Same parameters as Fig. 1 but with $q = 2^8$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Fig. 3.** Optimal values of $a$ with $m = 31, n = 33, k = 15, q = 2$ or $q = 2^8$, for MM-$\mathbb{F}_q$ and SM-$\mathbb{F}_{q^m}^+$.</figcaption></figure>

the MM-$\mathbb{F}_q$ and SM-$\mathbb{F}_{q^m}^+$ algebraic attacks are particularly more efficient than combinatorial attacks when, roughly, $r$ is small and $m$ is not too small (typically the case of original LRPC parameters).

Regarding the case of the harder zone typically used in code-based cryptography, namely $m = n, k = n/2$ and $r$ close to the Rank Gilbert-Varshamov bound,
our results seem to indicate that all attacks, both algebraic and combinatorial, have similar complexities. Surprisingly enough, this seems to remain true even in the case of greater value of $q$ ($q > 2$).

## Conclusion

We have presented here a new algebraic modeling for the RD problem, $\mathbb{F}_{q^m}^+$, that takes advantage of the $\mathbb{F}_{q^m}$-linearity of the problem to adapte the Support Minors Modeling $\text{SM-}\mathbb{F}_q$ for MinRank instances to the RD case. This modeling extends the MaxMinors Modeling $\text{MM-}\mathbb{F}_q$ for systems that are not overdetermined. We have given a proof for the number of linearly independent polynomials in $\text{SM-}\mathbb{F}_{q^m}$, and good heuristic explanation for the number of linearly independent polynomials in $\text{SM-}\mathbb{F}_{q^m}^+$.

From the computational point of view, when the field $q$ is small, the $\text{MM-}\mathbb{F}_q$ Modeling is faster to solve than the combinatorial approach, whereas it is the opposite for $r$ close to the rank GV bound. However, when $q$ increases, the algebraic approaches $\text{MM-}\mathbb{F}_q$ and $\text{SM-}\mathbb{F}_{q^m}^+$ becomes faster, and for small values of $r$ the $\text{SM-}\mathbb{F}_{q^m}^+$ Modeling beats the $\text{MM-}\mathbb{F}_q$ Modeling.

Finally, we have proposed an hybrid approach that reduces the solving of a MinRank (resp. RD) instance to the solving of several smaller instances. This has the advantage to apply to any solving algorithm for MinRank (resp. RD).

**Acknowledgements.** The authors thank the reviewers for their careful reading of the paper and their helpful comments.

This research was funded by the French *Agence Nationale de la Recherche* and *plan France 2030* program under grant ANR-22-PETQ-0008 PQ-TLS.

## References

1. Aguilar Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.C., Gaborit, P., Hauteville, A., Zémor, G.: Ouroboros-R. First round submission to the NIST post-quantum cryptography call (Nov 2017), https://pqc-ouroborosr.org

2. Aguilar Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.C., Gaborit, P., Zémor, G.: Rank quasi cyclic (RQC). First round submission to the NIST post-quantum cryptography call (Nov 2017), https://pqc-rqc.org

3. Aguilar Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Bros, M., Couvreur, A., Deneuville, J.C., Gaborit, P., Zémor, G., Hauteville, A.: Rank quasi cyclic (RQC). Second Round submission to NIST Post-Quantum Cryptography call (Apr 2020), https://pqc-rqc.org

4. Aguilar Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.C., Gaborit, P., Zémor, G., Couvreur, A., Hauteville, A.: Rank quasi cyclic (RQC). Second round submission to the NIST post-quantum cryptography call (Apr 2019), https://pqc-rqc.org
5. Aguilar Melchor, C., Aragon, N., Dyseryn, V., Gaborit, P., Zémor, G.: LRPC codes with multiple syndromes: near ideal-size KEMs without ideals. ArXiv abs/2206.11961 (2022)

6. Alagic, G., Jacob, A., Apon, D., Cooper, D., Dang, Q., Kelsey, J., Liu, Y.K., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Smith-Tone, D.: Status report on the second round of the NIST post-quantum cryptography standardization process. Tech. Rep. NISTIR 8309, NIST (Jul 2020). https://doi.org/10.6028/NIST.IR.8309, https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf

7. Aragon, N., Blazy, O., Deneuville, J.C., Gaborit, P., Hauteville, A., Ruatta, O., Tillich, J.P., Zémor, G.: LAKE – Low rAnk parity check codes Key Exchange. First round submission to the NIST post-quantum cryptography call (Nov 2017), https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/LAKE.zip

8. Aragon, N., Blazy, O., Deneuville, J.C., Gaborit, P., Hauteville, A., Ruatta, O., Tillich, J.P., Zémor, G.: LOCKER – LOw rank parity ChecK codes EncRyption. First round submission to the NIST post-quantum cryptography call (Nov 2017), https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/LOCKER.zip

9. Aragon, N., Blazy, O., Deneuville, J.C., Gaborit, P., Hauteville, A., Ruatta, O., Tillich, J.P., Zémor, G., Aguilar Melchor, C., Bettaieb, S., Bidoux, L., Bardet, M., Otmani, A.: ROLLO (merger of Rank-Ouroboros, LAKE and LOCKER). Second round submission to the NIST post-quantum cryptography call (Mar 2019), https://pqc-rollo.org

10. Aragon, N., Blazy, O., Gaborit, P., Hauteville, A., Zémor, G.: Durandal: a rank metric based signature scheme. In: Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part III. LNCS, vol. 11478, pp. 728-758. Springer (2019). https://doi.org/10.1007/978-3-030-17659-4_25, https://doi.org/10.1007/978-3-030-17659-4_25

11. Aragon, N., Gaborit, P., Hauteville, A., Ruatta, O., Zémor, G.: Ranksign – a signature proposal for the NIST’s call. First round submission to the NIST post-quantum cryptography call (Nov 2017), https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/RankSign.zip

12. Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.P.: Improvement of Generic Attacks on the Rank Syndrome Decoding Problem (Oct 2017), https://hal.archives-ouvertes.fr/hal-01618464, working paper or preprint

13. Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.P.: A new algorithm for solving the rank syndrome decoding problem. In: 2018 IEEE International Symposium on Information Theory, ISIT 2018, Vail, CO, USA, June 17-22, 2018. pp. 2421-2425. IEEE (2018). https://doi.org/10.1109/ISIT.2018.8437464

14. Baena, J., Briaud, P., Cabarcas, D., Perlner, R.A., Smith-Tone, D., Verbel, J.A.: Improving support-minors rank attacks: applications to GeMSS and Rainbow. IACR Cryptol. ePrint Arch., accepted for publication in CRYPTO 2022 p. 1677 (2021), https://eprint.iacr.org/2021/1677

15. Bardet, M., Briaud, P.: An algebraic approach to the rank support learning problem. In: Cheon, J.H., Tillich, J.P. (eds.) Post-Quantum Cryptography. LNCS, vol. 12841, pp. 442-462. Springer International Publishing, Cham (2021)
16. Bardet, M., Briaud, P., Bros, M., Gaborit, P., Neiger, V., Ruatta, O., Tillich, J.: An algebraic attack on rank metric code-based cryptosystems. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology – EUROCRYPT 2020. pp. 64–93. Springer International Publishing, Cham (2020), http://arxiv.org/abs/1910.00810

17. Bardet, M., Bros, M., Cabarcas, D., Gaborit, P., Perlner, R., Smith-Tone, D., Tillich, J.P., Verbel, J.: Improvements of algebraic attacks for solving the rank decoding and minrank problems. In: Advances in Cryptology - ASIACRYPT 2020, International Conference on the Theory and Application of Cryptology and Information Security, 2020. Proceedings. pp. 507–536 (2020). https://doi.org/10.1007/978-3-030-64837-4_17, https://dx.doi.org/10.1007/978-3-030-64837-4_17

18. Bellini, E., Caullery, F., Gaborit, P., Manzano, M., Mateu, V.: Improved Veron identification and signature schemes in the rank metric. In: Proc. IEEE Int. Symposium Inf. Theory - ISIT 2019. vol. abs/1903.10212, pp. 1872–1876. IEEE, Paris, France (Jul 2019)

19. Bellini, E., Esser, A., Sanna, C., Verbel, J.: MR-DSS – Smaller MinRank-based (Ring-)Signatures. In: Cheon J.H., J.T. (ed.) Post-Quantum Cryptography 2022. LNCS, vol. 13512. Springer (Sep 2022), https://eprint.iacr.org/2022/973

20. Bellini, E., Esser, A., Sanna, C., Verbel, J.: MR-DSS – Smaller MinRank-based (Ring-)Signatures. IACR Cryptology ePrint Archive, Report 2022/973 (Oct 2022), https://eprint.iacr.org/2022/973, version 20220921:142218

21. Bellini, E., Gaborit, P., Hasikos, A., Mateu, V.: Enhancing code based zero-knowledge proofs using rank metric. In: Krenn, S., Shulman, H., Vaudenay, S. (eds.) Cryptology and Network Security - 19th International Conference, CANS 2020, Vienna, Austria, December 14-16, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12579, pp. 570–592. Springer (2020). https://doi.org/10.1007/978-3-030-65411-5_28, https://doi.org/10.1007/978-3-030-65411-5_28

22. Beullens, W.: Improved cryptanalysis of UOV and Rainbow. In: Canteaut, A., Standaert, F.X. (eds.) Advances in Cryptology – EUROCRYPT 2021. Lecture Notes in Computer Science, vol. 12696, pp. 348–373. Springer International Publishing (2021). https://doi.org/10.1007/978-3-030-77870-5_13, https://doi.org/10.1007/978-3-030-77870-5_13

23. Beullens, W.: Breaking Rainbow takes a weekend on a laptop. In: Advances in Cryptology - CRYPTO 2022. LNCS, Springer-Verlag (2022), https://eprint.iacr.org/2022/214

24. Bidoux, L., Briaud, P., Bros, M., Gaborit, P.: RQC revisited and more cryptanalysis for rank-based cryptography. ArXiv abs/2207.01410 (2022)

25. Bruns, W., Vetter, U.: Determinantal Rings, lncs, vol. 1327. Springer (1988)

26. Buss, J.F., Frandsen, G.S., Shallit, J.O.: The computational complexity of some problems of linear algebra. J. Comput. System Sci. 58(3), 572–596 (Jun 1999)

27. Cabarcas, D., Smith-Tone, D., Verbel, J.: Key recovery attack for ZHFE. In: Post-Quantum Cryptography 2017. LNCS, vol. 10346, pp. 289–308. Utrecht, The Netherlands (Jun 2017). https://doi.org/10.1007/978-3-319-59879-6_17, https://doi.org/10.1007/978-3-319-59879-6_17

28. Chabaud, F., Stern, J.: The cryptographic security of the syndrome decoding problem for rank distance codes. In: Advances in Cryptology - ASIACRYPT 1996. LNCS, vol. 1163, pp. 368–381. Springer, Kyongju, Korea (Nov 1996)

29. Courtois, N.: Efficient zero-knowledge authentication based on a linear algebra problem MinRank. In: Advances in Cryptology - ASIACRYPT 2001. LNCS, vol. 2248, pp. 402–421. Springer, Gold Coast, Australia (2001), https://doi.org/10.1007/3-540-45682-1_24
30. Couvreur, A., Gaborit, P., Gauthier-Umaña, V., Otmani, A., Tillich, J.P.: Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes. Des. Codes Cryptogr. 73(2), 641–666 (2014)

31. Cox, D., Little, J., O'Shea, D.: Ideals, Varieties, and algorithms: an Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics, Springer-Verlag, New York. (2015). https://doi.org/10.1007/978-3-319-16721-3

32. Debris-Alazard, T., Tillich, J.P.: A polynomial attack on a NIST proposal: Ranksign, a code-based signature in rank metric. preprint (Apr 2018), https://eprint.iacr.org/2018/339.pdf, IACR Cryptology ePrint Archive

33. Faugère, J.C., Levy-dit-Vehel, F., Perret, L.: Cryptanalysis of Minrank. In: Wagner, D. (ed.) Advances in Cryptology - CRYPTO 2008. LNCS, vol. 5157, pp. 280–296 (2008), https://doi.org/10.1007/978-3-540-85174-5_16

34. Gabidulin, E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985)

35. Gabidulin, E.M., Paramonov, A.V., Tretjakov, O.V.: Ideals over a non-commutative ring and their applications to cryptography. In: Advances in Cryptology - EUROCRYPT'91. pp. 482–489. No. 547 in LNCS, Brighton (Apr 1991)

36. Gaborit, P., Hauteville, A., Phan, D.H., Tillich, J.P.: Identity-based encryption from rank metric. In: Advances in Cryptology - CRYPTO (2017), https://doi.org/10.1007/978-3-319-63697-9_7

37. Gaborit, P., Murat, G., Ruatta, O., Zémor, G.: Low rank parity check codes and their application to cryptography. In: Proceedings of the Workshop on Coding and Cryptography WCC'2013. Bergen, Norway (2013), www.selmer.uib.no/WCC2013/pdfs/Gaborit.pdf

38. Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. IEEE Trans. Inform. Theory 62(2), 1006–1019 (2016)

39. Gaborit, P., Ruatta, O., Schrek, J., Zémor, G.: New results for rank-based cryptography. In: Progress in Cryptology - AFRICACRYPT 2014. LNCS, vol. 8469, pp. 1–12 (2014)

40. Gaborit, P., Schrek, J., Zémor, G.: Full cryptanalysis of the chen identification protocol. In: Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29 - December 2, 2011. Proceedings. pp. 35–50 (2011). https://doi.org/10.1007/978-3-642-25405-5_3

41. Gaborit, P., Zémor, G.: On the hardness of the decoding and the minimum distance problems for rank codes. IEEE Trans. Inform. Theory 62(12), 7245–7252 (2016)

42. Goubin, L., Courtois, N.: Cryptanalysis of the TTM cryptosystem. In: Okamoto, T. (ed.) Advances in Cryptology - ASIACRYPT 2000. LNCS, vol. 1976, pp. 44–57. Springer (2000)

43. Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryptosystem. In: Buhler, J. (ed.) Algorithmic Number Theory, Third International Symposium, ANTS-III, Portland, Oregon, USA, June 21-25, 1998, Proceedings. LNCS, vol. 1423, pp. 267–288. Springer (1998)

44. Kipnis, A., Shamir, A.: Cryptanalysis of the HFE public key cryptosystem by relin-earization. In: Advances in Cryptology - CRYPTO'99. LNCS, vol. 1666, pp. 19–30. Springer, Santa Barbara, California, USA (Aug 1999). https://doi.org/10.1007/3-540-48405-1, https://doi.org/10.1007/3-540-48405-1_2

45. Levy-dit-Vehel, F., Perret, L.: Algebraic decoding of rank metric codes. Talk at the Special Semester on Gröbner Bases - Workshop D1 pp. 1–19 (2006), https://ricamwww.ricam.oeaw.ac.at/specsem/srs/groeb/download/Levy.pdf
46. Loidreau, P.: Asymptotic behaviour of codes in rank metric over finite fields. Des. Codes Cryptogr. 71(1), 105–118 (2014)

47. Misoczki, R., Tillich, J.P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: New McEliece variants from moderate density parity-check codes (2012). https://doi.org/10.1109/ISIT.2013.6620590, http://eprint.iacr.org/2012/409

48. Ourivski, A.V., Johansson, T.: New technique for decoding codes in the rank metric and its cryptography applications. Problems of Information Transmission 38(3), 237–246 (2002). https://doi.org/10.1023/A:1020369320078

49. Overbeck, R.: A new structural attack for GPT and variants. In: Mycrypt. LNCS, vol. 3715, pp. 50–63 (2005)

50. Petzoldt, A., Chen, M., Yang, B., Tao, C., Ding, J.: Design principles for HFEv-based multivariate signature schemes. In: Iwata, T., Cheon, J.H. (eds.) Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part I. LNCS, vol. 9452, pp. 311–334. Springer (2015). https://doi.org/10.1007/978-3-662-48797-6\_14, https://doi.org/10.1007/978-3-662-48797-6\_14

51. Sidelnikov, V.M., Shestakov, S.: On the insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Math. Appl. 1(4), 439–444 (1992)

52. Stern, J.: A new identification scheme based on syndrome decoding. In: Stinson, D. (ed.) Advances in Cryptology - CRYPTO'93. LNCS, vol. 773, pp. 13–21. Springer (1993)

53. Tao, C., Petzoldt, A., Ding, J.: Efficient key recovery for all HFE signature variants. In: Malkin, T., Peikert, C. (eds.) Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part I. Lecture Notes in Computer Science vol. 12825, pp. 70–93. Springer (2021). https://doi.org/10.1007/978-3-030-84242-0\_4, https://doi.org/10.1007/978-3-030-84242-0\_4

54. Verbel, J., Baena, J., Cabarcas, D., Perlner, R., Smith-Tone, D.: On the complexity of “superdetermined” Minrank instances. In: Post-Quantum Cryptography 2019. LNCS, vol. 11505, pp. 167–186. Springer, Chongqing, China (May 2019). https://doi.org/10.1007/978-3-030-25510-7\_10, https://doi.org/10.1007/978-3-030-25510-7\_10

## A Missing proofs from Section 3

It will be helpful to notice that Fact 1 implies

**Lemma 4.** Let $T \subset \{1..n-k-1\}$, then

$$|\mathbf{H}_y|_{T,T+k+1} = 1 \qquad (23)$$

$$|\mathbf{H}_y|_{T,I} = 0 \quad \text{if } I \cap \{k+2..n\} \not\subseteq T+k+1 \qquad (24)$$

*Proof.* This follows immediately from the fact that $\mathbf{H}_y$ is in systematic form in its $n-k-1$ last coordinates (i.e. for the positions $j \in \{k+2..n\}$): $\mathbf{H}_y = (*\mathbf{I}_{n-k-1})$. Indeed $|\mathbf{H}_y|_{T,T+k+1} = |\mathbf{I}_s| = 1$ where $s = \#T$. The other minor is 0 since it contains a column which is 0. $\square$
## A.1 Proof of Proposition 1

Let us recall this proposition.

**Proposition 1.** The polynomials in $Q_0$ can be obtained as linear combinations between the polynomials in $Q_{\ge 1}$:

$$Q_{T+k+1} = - \sum_{Q_I \in Q_{\ge 1}} |\mathbf{H}_y|_{T,I} Q_I, \quad \forall T \subset \{1..n-k-1\}, \ #T = r+1. \quad (25)$$

*Proof.* We first observe that $Q$ in $Q_0$ is of the form $Q_{T+k+1}$ with $T \subset \{1..n-k-1\}$, $\#T = r+1$. By definition we have $(\mathbf{x}G + \mathbf{y})\mathbf{H}_y^T = 0$ and hence by using the Cauchy-Binet formula (3) we obtain

$$0 = \left| \left( \begin{array}{c} \mathbf{x}G + \mathbf{y} \\ C \end{array} \right) \mathbf{H}_y^T \right|_{*,T} = \sum_{\substack{I \subset \{1..n\} \\ \#I = r+1}} |\mathbf{H}_y|_{T,I} Q_I.$$

We then use Lemma 4: $|\mathbf{H}_y|_{T,T+k+1} = 1$, and $|\mathbf{H}_y|_{T,I} = 0$ if $I \subset \{k+2..n\}$, $I \ne T+k+1$. The previous equation expresses $Q_{T+k+1} \in Q_0$ in terms of the $Q_I$'s in $Q_{\ge 1}$, namely $Q_{T+k+1} = -\sum_{Q_I \in Q_{\ge 1}} |\mathbf{H}_y|_{T,I} Q_I$. $\square$

## A.2 Proofs of Propositions 2 and 3

For the proofs of Propositions 3 and 2, we recall that we use the grevlex monomial ordering on the variables $x_1 > \cdots > x_k > c_T$ with the $c_T$'s ordered according to a reverse lexicographical ordering on $T$: $c_{T'} > c_T$ if $t'_j = t_j$ for $j < j_0$ and $t'_{j_0} > t_{j_0}$ where $T = \{t_1 < \cdots < t_r\}$ and $T' = \{t'_1 < \cdots < t'_r\}$. We denote by $\text{LT}(f)$ the leading term of a polynomial $f$ with respect to this term order.

We will also make use of the following lemma.

**Lemma 5.** Let $Q_I$ be an equation in $Q_{\ge 2}$. We have

$$\text{LT}(Q_I) = x_{i_1} c_{I_1} \\ Q_I = x_{i_1} c_{I_1} \underbrace{- \mathbf{x}G_{*,i_2} c_{I_2} + \cdots + (-1)^r \mathbf{x}G_{*,i_{r+1}} c_{I_{r+1}}}_{\text{smaller terms of degree 2}} \\ \underbrace{- y_{i_2} c_{I_2} + \cdots + (-1)^r y_{i_{r+1}} c_{I_{r+1}}}_{\text{smaller terms of degree 1}}$$

where $I = \{i_1 < \cdots < i_{r+1}\}$ and $I_1 := I \setminus \{i_1\}$. The leading terms of such $Q_I$'s are all different and the variables $\{c_{J+k+1}\}_{J \subset \{1..n-k-1\}}$ do not appear in $Q_I$.

*Proof.* Since $Q_I$ is in $Q_{\ge 2}$ we know that $i_1 \le k$. We have

$$Q_I = \left| \begin{pmatrix} \mathbf{x}G + \mathbf{y} \\ C \end{pmatrix} \right|_{*,I} = \sum_{i_u \in I} (-1)^{1+u} (\mathbf{x}G_{*,i_u} + y_{i_u}) c_{I \setminus \{i_u\}}.$$
Taking $\mathbf{G}$ and $\mathbf{y}$ as in Fact 1, for any $i_u \in I^- = I \cap \{1..k\}$ (and at least $i_1 \in I^-$ by assumption), we have $\mathbf{x}\mathbf{G}_{*,i_u} + \mathbf{y}_{i_u} = x_{i_u}$. Let $I_u = I \setminus \{i_u\}$ for $1 \le u \le r+1$, then for the chosen ordering we have $I_1 > I_2 > \cdots > I_{r+1}$. The ordered terms in $Q_I$ are then

$$Q_I = x_{i_1} c_{I_1} \underbrace{-\mathbf{x}\mathbf{G}_{*,i_2} c_{I_2} + \cdots + (-1)^r \mathbf{x}\mathbf{G}_{*,i_{r+1}} c_{I_{r+1}}}_{\text{smaller terms of degree 2}} \\ -\underbrace{-y_{i_2} c_{I_2} + \cdots + (-1)^r y_{i_{r+1}} c_{I_{r+1}}}_{\text{smaller terms of degree 1}}$$

so that $\mathrm{LT}(Q_I) = x_{i_1}c_{I_1}$ and these leading terms are different for all the equations. For the last point, we observe that $\{i_1 < i_2\} \subset \{1..k+1\}$. This implies that for any $i_u \in I$, the set $I \setminus \{i_u\}$ contains at least one of $i_1, i_2$ so that it is not included in $\{k+2..n\}$, from which it follows that the variables $\{c_{J+k+1}\}_{J \subset \{1..n-k-1\}}$ do not appear in $Q_I$. $\square$

We are ready now to prove Proposition 2:

**Proposition 2.** The polynomials in $\mathcal{P} \cup Q_{\ge 2}$ are linearly independent, as

$$\mathrm{LT}(P_J) = c_{J+k+1} \qquad (P_J \in \mathcal{P}) \\ \mathrm{LT}(Q_I) = x_{i_1} c_{I \setminus \{i_1\}} \qquad (Q_I \in Q_{\ge 2}, i_1 = \min(I))$$

Moreover, each variable $c_{J+k+1}$ for any $J \subset \{1..n-k-1\}$, $\#J = r$ appears only as the leading term of $P_J$ and does not appear in any of the polynomials in $Q_{\ge 2}$ nor in $P_{J'}$ with $J' \ne J$.

*Proof.* Lemma 4 already proves that the equations in $Q_{\ge 2}$ are linearly independent. Consider now a $P_J \in \mathcal{P}$. Here $J \subset \{1..n-k-1\}$, $\#J = r$. By using the special shape of $\mathbf{H}_y$ we have

$$P_J = |CH_y^T|_{*,J} = \sum_{\substack{T \subset \{1..n\} \\ \#T=r}} c_T |\mathbf{H}_y|_{J,T} = \sum_{\substack{T \subset \{1..n\}, \#T=r, \\ T \cap \{k+2..n\} \subset J+k+1}} c_T |\mathbf{H}_y|_{J,T} \\ = c_{J+k+1} + \sum_{\substack{T \subset \{1..n\}, \#T=r, \\ T \cap \{k+2..n\} \subset J+k+1, T \cap \{1..k+1\} \ne \emptyset}} c_T |\mathbf{H}_y|_{J,T}$$

We used here again Lemma 4. Note that the $c_T$'s in the sum are all smaller than $c_{J+k+1}$, so that $c_{J+k+1}$ is the leading term of $P_J$ and does not appear in any other $P_{J'}$. This shows that the polynomials in $\mathcal{P} \cup Q_{\ge 2}$ are linearly independent, as they have distinct leading terms, and concludes the proof of Proposition 2. $\square$

Let us now recall Proposition 3 before proving it.

**Proposition 3.** The polynomials in $Q_1$ generate the same $\mathbb{F}_{q^m}$-vector space as the polynomials

$$\mathcal{P} \cup \bigcup_{j=1}^{k} x_j \mathcal{P}$$
modulo the polynomials in $Q_{\ge 2}$. More precisely, for any $J \subset \{1..n-k-1\}$, $\#J = r$ and $j \in \{1..k\}$ we have

$$P_J = Q_{\{k+1\} \cup (J+k+1)} + \sum_{Q_I \in Q_{\ge 2}} (-1)^r |\mathbf{H}|_{J \cup \{n-k\}, I} Q_I$$
$$x_j P_J = Q_{\{j\} \cup (J+k+1)} + \sum_{Q_I \in Q_{\ge 2}, j \in I} (-1)^{1+\mathrm{Pos}(j,I)} |\mathbf{H}_{\mathbf{y}}|_{J,I \setminus \{j\}} Q_I$$

where $\mathrm{Pos}(i_u, I) = u$ for $I = \{i_1, \dots, i_{r+1}\}$ such that $i_1 < \dots < i_{r+1}$.

*Proof.* Consider $\left| \begin{pmatrix} x\mathbf{G} + \mathbf{y} \\ \mathbf{C} \end{pmatrix} \mathbf{H}^\top \right|_{*, J \cup \{n-k\}}$. On one hand, we have with the Cauchy-Binet formula

$$\left| \begin{pmatrix} x\mathbf{G} + \mathbf{y} \\ \mathbf{C} \end{pmatrix} \mathbf{H}^{\top} \right|_{*, J \cup \{n-k\}} = \sum_{I \subset \{1..n\}, \#I=r+1} |\mathbf{H}|_{J \cup \{n-k\}, I} Q_I. \quad (26)$$

On the other hand, we use the particular shapes for $\mathbf{H}$, $\mathbf{y}$ and $\mathbf{h}$ given in Fact 1:

$$\begin{aligned}
\mathbf{H} &= \begin{pmatrix} \mathbf{H}_{\mathbf{y}} \\ \mathbf{h} \end{pmatrix} \\
\mathbf{y} &= \begin{pmatrix} 0_k & 1 \end{pmatrix} \\
\mathbf{h} &= \begin{pmatrix} 1 & 0_{n-k-1} \end{pmatrix}
\end{aligned}$$

and obtain

$$\begin{pmatrix} x\mathbf{G} + \mathbf{y} \\ \mathbf{C} \end{pmatrix} \mathbf{H}^{\top} = \begin{pmatrix} \mathbf{y}\mathbf{H}^{\top} \\ C\mathbf{H}^{\top} \end{pmatrix} = \begin{pmatrix} \mathbf{y}\mathbf{H}_{\mathbf{y}}^{\top} & \mathbf{y}\mathbf{h}^{\top} \\ C\mathbf{H}_{\mathbf{y}}^{\top} & C\mathbf{h}^{\top} \end{pmatrix} = \begin{pmatrix} 0_{n-k-1} & 1 \\ C\mathbf{H}_{\mathbf{y}}^{\top} & C\mathbf{h}^{\top} \end{pmatrix},$$

so that for any $J \subset \{1..n-k-1\}$, $\#J = r$ we get

$$\left| \begin{pmatrix} x\mathbf{G} + \mathbf{y} \\ \mathbf{C} \end{pmatrix} \mathbf{H}^{\top} \right|_{*, J \cup \{n-k\}} = \left| \begin{pmatrix} \mathbf{0} \\ C\mathbf{H}_{\mathbf{y}}^{\top} \end{pmatrix} \begin{pmatrix} 1 \\ C\mathbf{h}^{\top} \end{pmatrix} \right|_{*, J \cup \{n-k\}} = (-1)^r \left| C\mathbf{H}_{\mathbf{y}}^{\top} \right|_{*, J} = (-1)^r P_J.$$

By using

$$|\mathbf{H}|_{J \cup \{n-k\}, I} = \begin{cases} 0 & \text{if } I \cap \{k+2..n\} \not\subset J+k+1 \\ (-1)^r & \text{if } I = \{k+1\} \cup (J+k+1), \end{cases}$$

we then have $P_J = \underbrace{Q_{\{k+1\} \cup (J+k+1)}}_{\in Q_1} + (-1)^r \sum_{Q_I \in Q_{\ge 2}} |\mathbf{H}|_{J \cup \{n-k\}, I} Q_I$.

This gives a one-to-one correspondence between equations $P_J$ and equations $Q_{\{k+1\} \cup J+k+1} \in Q_1$. It remains to show that the $Q_{\{i_1\} \cup J+k+1} \in Q_1$ with $i_1 \le k$ reduce to $x_{i_1} P_J$ modulo $Q_{\ge 2}$.
If $g_{i_1} := G_{\{i_1\},*}$, we consider $H_{i_1}$ a parity-check matrix of the code $C_{i_1} := \langle y, g_1, \dots, g_{i_1-1}, g_{i_1+1}, \dots, g_k \rangle$ such that $H_{i_1}^T = (H_y^T e_{i_1})^T$ and where $e_{i_1}$ is the $i_1$-th canonical basis vector in $\mathbb{F}_q^n$. Since $g_{i_1} e_{i_1}^T = 1$, we have

$$ \begin{pmatrix} xG + y \\ C \end{pmatrix} H_{i_1}^T = \begin{pmatrix} x_{i_1} g_{i_1} H_{i_1}^T \\ C H_{i_1}^T \end{pmatrix} = \begin{pmatrix} 0 & x_{i_1} \\ C H_y^T C e_{i_1} \end{pmatrix}^T. $$

For $J \subset \{1..n-k-1\}$, $\#J = r$, one obtains

$$ \left| \begin{pmatrix} xG + y \\ C \end{pmatrix} H_{i_1}^T \right|_{*, J \cup \{n-k\}} = \left| \begin{pmatrix} 0 & x_{i_1} \\ C H_y^T C h_{i_1}^T \end{pmatrix} \right|_{*, J \cup \{n-k\}} \\ = \sum_{I \subset \{1..n\}, \#I=r+1} |H_{i_1}|_{J \cup \{n-k\}, I} Q_I = (-1)^r x_{i_1} \left| C H_y^T \right|_{*, J} = (-1)^r x_{i_1} P_J. $$

By Laplace expansion along the last row, we have $|H_{i_1}|_{J \cup \{n-k\}, I} = 0$ if $i_1 \notin I$ and $|H_{i_1}|_{J \cup \{n-k\}, I} = (-1)^{r+1+\mathrm{Pos}(i_1, I)} |H_y|_{J, I \setminus \{i_1\}}$ if $i_1 \in I$, where $\mathrm{Pos}(i_1, I)$ denotes the position of $i_1$ in the ordered set $I$ (1 if it is the first element). We deduce from this that

$$ \begin{aligned} x_{i_1} P_J &= \sum_{I \subset \{1..n\}, \#I=r+1, i_1 \in I} (-1)^{1+\mathrm{Pos}(i_1, I)} |H_y|_{J, I \setminus \{i_1\}} Q_I \\ &= Q_{\{i_1\} \cup (J+k+1)} + \sum_{Q_I \in \mathcal{Q}_{\ge 2}, i_1 \in I} (-1)^{1+\mathrm{Pos}(i_1, I)} |H_y|_{J, I \setminus \{i_1\}} Q_I. \end{aligned} $$

Note that by the previous results, $\mathrm{LT}(Q_{\{i_1\}+J+k+1}) = x_{i_1} c_{J+k+1}$ so that all equations in $\mathcal{P} \cup \bigcup_{j=1}^k x_j \mathcal{P} \cup \mathcal{Q}_{\ge 2}$ are linearly independent.

## A.3 Proof of Proposition 4

Let us first recall this proposition.

**Proposition 4.** For any $b \ge 1$, the $\mathbb{F}_{q^m}$-vector space generated by the polynomials $\mathcal{Q}_{\ge 2}$ augmented at bi-degree $(b, 1)$ by multiplying by monomials of degree $b-1$ in the $x_i$ variables admits the following basis:

$$ \mathcal{B}_b = \left\{ x_{i_1}^{\alpha_{i_1}} \dots x_k^{\alpha_k} Q_I : \begin{subarray}{l} I = \{i_1 < i_2 < \dots < i_{r+1}\}, \\ i_2 \le k+1, \sum_{j \ge i_1} \alpha_j = b-1 \end{subarray} \right\} \quad (27) $$

In particular, it has dimension

$$ \mathcal{N}_b^{\mathbb{F}_{q^m}} := \sum_{i=1}^{k} \binom{n-i}{r} \binom{k+b-1-i}{b-1} - \binom{n-k-1}{r} \binom{k+b-1}{b}, \quad (28) $$

and there are

$$ \mathcal{M}_b^{\mathbb{F}_{q^m}} := \binom{k+b-1}{b} \left( \binom{n}{r} - \binom{n-k-1}{r} \right) \quad (29) $$

monomials of degree $(b, 1)$. We have $\mathcal{N}_b^{\mathbb{F}_{q^m}} < \mathcal{M}_b^{\mathbb{F}_{q^m}} - 1$ for any $b \ge 1$.
Proof. The set $\mathcal{B}_b$ clearly contains linearly independent equations, since their leading terms are all different:

$$ \mathrm{LT}(x_{i_1}^{\alpha_{i_1}} \dots x_k^{\alpha_k} Q_I) = x_{i_1}^{\alpha_{i_1}+1} \dots x_k^{\alpha_k} c_{I\setminus\{i_1\}}. $$

The number of polynomials in $\mathcal{B}_b$ is the number of sets $I$ and $(\alpha_{i_1}, \dots, \alpha_k)$:

$$ \mathcal{N}_b^{\mathcal{F}^{q_m}} = \sum_{i_1=1}^{k} \sum_{i_2=i_1+1}^{k+1} \binom{n-i_2}{r-1} \binom{k-i_1+1+b-2}{b-1} $$

which gives Eq. (28), considering the identities $\sum_{i_2=i_1+1}^{k+1} \binom{n-i_2}{r-1} = \binom{n-i_1}{r} - \binom{n-k-1}{r}$ and $\sum_{i_1=1}^{k} \binom{k-i_1+1+b-2}{b-1} = \binom{k+b-1}{b}$. The number of monomials comes from the fact that the variables $c_{J+k+1}$ do not appear in $Q_{\ge 2}$. The inequality $\mathcal{N}_b < \mathcal{M}_b - 1$ is easy to derive using previous identities and $\binom{n-i_1}{r} < \binom{n-1}{r}$ for all $i_1 \ge 1$.

We will now show that the polynomials $x_j Q_I$ for $1 \le j < i_1$, $Q_I \in Q_{\ge 2}$ reduce to zero modulo $\mathcal{B}_2$, which is sufficient to conclude the proof. The number of such polynomials is equal to the number of sets $K = \{k_1 < k_2 < \dots < k_{r+2}\} \subset \{1..n\}$ such that $k_3 \le k+1$, and we are going to construct the same number of independent syzygies between the polynomials at bi-degree (2, 1). Indeed, for any such $K$, we have the relation

$$ \left| \begin{pmatrix} xG + y \\ xG + y \\ C \end{pmatrix} \right|_{*,K} = 0. \qquad (30) $$

By Laplace expansion along the first row, one obtains

$$ 0 = x_{k_1} Q_{\{k_2, \dots, k_{r+2}\}} - \sum_{u=2}^{r+2} (-1)^u \left( \sum_{j=1}^{k} x_j G_{j,k_u} + y_{k_u} \right) Q_{K \setminus \{k_u\}}. $$

Since $|K \cap \{1..k+1\}| \ge 3$, we obtain syzygies between the relevant $Q_I$, say those such that $|I \cap \{1..k+1\}| \ge 2$. We will now show that those syzygies are linearly independent. To this end, we order the $Q_I$'s according to a grevlex order on the subsets $I$ as for the $c_T$ variables. The largest $Q_I$ is $Q_{\{n-r..n\}}$, the smallest one is $Q_{\{1..r+1\}}$. The syzygy associated to $K$ is given by

$$ \mathcal{G}^K := \left( \underbrace{0}_{I \not\subset K}, \underbrace{(-1)^{1+u} \sum_{j=1}^{k} x_j \mathbf{G}_{j,k_u} + \mathbf{y}_{k_u}}_{K \setminus I = \{k_u\}} \right)_{I \subset \{1..n\}, \#I=r+1}. $$

The largest set $I$ such that the coefficient in front of $Q_I$ in $\mathcal{G}^K$ is non-zero is $I = K_1 = K \setminus \{k_1\}$ and this coefficient is $x_{k_1}$. The syzygies which have the same leading position $Q_{K_1}$ as $\mathcal{G}^K$ are the $\mathcal{G}^{K_1 \cup \{j\}}$ for $1 \le j < k_1$. Finally, the highest degree part in the coefficient in front of $Q_{K_1}$ in $\mathcal{G}^{K_1 \cup \{j\}}$ is $x_j$, which shows that all the $\mathcal{G}^{K_1 \cup \{j\}}$ are linearly independent for $1 \le j \le k_1$. $\square$
### A.4 Proof of Proposition 8

Let us recall this proposition.

**Proposition 8.** For any $T \subset \{1..n-k-1\}$, $\#T = r+1$ and $1 \le i \le m$, we obtain a relation between the $\tilde{Q}_I$ polynomials given by

$$ \mathrm{Tr}(\beta_i^*) \tilde{Q}_{T+k+1} + \sum_{\substack{I \subset \{1..n\} \\ \#I=r+1 \\ I \cap \{k+1..n\} \subsetneq T+k+1}} \mathrm{Tr}(\beta_i^* | \mathbf{H}_y|_{T,I}) \tilde{Q}_I = 0. \quad (31) $$

Note that the coefficients of any of these relations belong to $\mathbb{F}_q$.

*Proof.* For this purpose, we introduce the $\ell$-th Frobenius iterate of the $P_J$'s, that has the advantage to satisfy the relation $|\mathbf{M}^{[\ell]}| = |\mathbf{M}|^{[\ell]}$ for any square matrix $\mathbf{M}$. This is equivalent to using the unfolded equations $P_{i,J}$ thanks to the following relation: for any $J \subset \{1..n-k-1\}$, $\#J = r$ we have

$$ \langle P_{i,J} : 1 \le i \le m \rangle_{\mathbb{F}_{q^m}} = \langle P_J^{[\ell]} : 0 \le \ell \le m-1 \rangle_{\mathbb{F}_{q^m}}. $$

Indeed, $P_{i,J} = \mathrm{Tr}(\beta_i^* P_J) = \sum_{\ell=0}^{m-1} (\beta_i^*)^{[\ell]} P_J^{[\ell]}$ and $P_J^{[\ell]} = \sum_{i=1}^m \beta_i^{[\ell]} P_{i,J}$.

For fixed $0 \le \ell \le m-1$ and $T \subset \{1..n-k-1\}$, $\#T = r+1$, we consider the minor

$$ \Gamma_{\ell,T} := \left| \begin{pmatrix} x\mathbf{G} + \mathbf{y} \\ \mathbf{C} \end{pmatrix} (\mathbf{H}_y^{[\ell]})^{\top} \right|_{*,T}. $$

By Laplace expansion along the first row, this minor can be viewed as a combination with coefficients in $\mathbb{F}_{q^m}[x_i]$ between maximal minors of $C(\mathbf{H}_y^{[\ell]})^{\top}_{*,T}$, and these minors are exactly the $P_J^{[\ell]}$'s for $J \subset T$. The normal form of $\Gamma_{\ell,T}$ with respect to $\langle P_{i,J} \rangle = \langle P_J^{[\ell]} \rangle$ is then 0. Also, using the Cauchy-Binet formula, each minor is a linear combination of the $Q_I$'s, given by

$$ \tilde{Q}_{T+k+1} + \sum_{\substack{I \subset \{1..n\}, \#I=r+1, \\ I \cap \{k+1..n\} \subsetneq T+k+1}} \tilde{Q}_I |\mathbf{H}_y^{[\ell]}|_{T,I} = 0. $$

To conclude the proof, we use the fact that the set of previous equations for all $0 \le \ell \le m-1$ generate the same vector space over $\mathbb{F}_{q^m}$ as the set of equations

$$ \mathrm{Tr}(\beta_i^*) \tilde{Q}_{T+k+1} + \sum_{\substack{I \subset \{1..n\} \\ \#I=r+1 \\ I \cap \{k+1..n\} \subsetneq T+k+1}} \mathrm{Tr}(\beta_i^* | \mathbf{H}_y|_{T,I}) \tilde{Q}_I = 0, $$

for all $1 \le i \le m$.

□