# Cryptanalysis of rank-metric schemes based on distorted Gabidulin codes

Pierre Briaud, Pierre Loidreau

► To cite this version:

Pierre Briaud, Pierre Loidreau. Cryptanalysis of rank-metric schemes based on distorted Gabidulin codes. PQCrypto 2023: The 14th International Conference on Post-Quantum Cryptography, Aug 2023, College Park, MD, United States. pp.38-56, 10.1007/978-3-031-40003-2_2. hal-04145226

HAL Id: hal-04145226

https://hal.science/hal-04145226

Submitted on 29 Jun 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 Attribution 4.0 International License
# Cryptanalysis of rank-metric schemes based on distorted Gabidulin codes

Pierre Briaud¹,² and Pierre Loidreau³

¹ Sorbonne Universités, UPMC Univ Paris 06

² Inria, Team COSMIQ, Paris, France
pierre.briaud@inria.fr

³ DGA and IRMAR, Univ. Rennes
pierre.loidreau@univ-rennes.fr

**Abstract.** In this work, we introduce a new attack for the Loidreau scheme [PQCrypto 2017] and its more recent variant LowMS. This attack is based on a constrained linear system for which we provide two solving approaches:

- the first one is an enumeration algorithm inspired from combinatorial attacks on the Rank Decoding (RD) Problem. While the attack technique remains very simple, it allows us to obtain the best known structural attack on the parameters of these two schemes.

- the second one is to rewrite it as a bilinear system over $\mathbb{F}_q$. Even if Gröbner basis techniques on this second system seem infeasible, we provide a detailed analysis of the first degree fall polynomials which arise when applying such algorithms.

## 1 Introduction

The idea of building rank-metric cryptography relying on Gabidulin codes is over 30 years old. It dates back to the seminal GPT scheme [15]. The initial goal of Gabidulin was to use the properties of the rank metric in order to propose a scheme with a public-key size one order of magnitude smaller than that of the original McEliece cryptosystem [20]. However, this proposal and following variants have suffered structural attacks [22] tending to show that masking these codes is difficult.

The Loidreau cryptosystem introduced in [19] is based on a different type of masking. Along with the LowMS variant [1], it is arguably one of the few reparations which resists cryptanalysis for well-chosen parameters.

On the one hand, this scheme offers nice features compared to other modern PKEs and especially to those proposed at the NIST post-quantum standardization process. First, decryption is deterministic. Second, regarding performance, the key is between one and two orders of magnitude smaller than that of non-structured Hamming-based cryptosystems. It even favorably compares with that of PKEs based on unstructured lattices. Similarly, the ciphertext is small compared to that of unstructured lattice proposals and it compares favourably with that of structured lattices.
On the other hand, its security analysis is not yet sufficiently stabilized. This is mainly due to the new type of masking, which calls for assessing the difficulty of distinguishing the public code from a random one. This code is a Gabidulin code distorted with a non-singular matrix with coefficients in a small-dimensional secret subspace of $\mathbb{F}_{q^m}$. A conjecture was made in [19] concerning the complexity of solving the problem, for parameters not impacted by the Coggia-Couvreur attack.

**Contributions.** First, we improve upon the enumeration approach of Loidreau presented as an extended abstract at the WCC 2022 conference. We adapt techniques from combinatorial attacks on RD [2] showing that it is more efficient to enumerate over vector spaces of larger dimension than that of the original secret subspace. This allows us to obtain the best complexity for this type of technique.

Second, we propose an algebraic approach to find a distinguisher by modeling the original problem as a bilinear system over $\mathbb{F}_q$. Even if the solving by Gröbner bases does not seem promising from our experiments, we manage to analyze precisely the first steps of the computation. In particular, we show that there exist degree falls of the same nature as in [4,6] due to the specific structure of the system.

## 2 Preliminaries on the rank metric

Rank-metric cryptography relies on codes which are $\mathbb{F}_{q^m}$-linear, where $\mathbb{F}_{q^m}$ is an extension of degree $m$ over $\mathbb{F}_q$. In this context, the rank (or weight) of a vector $\mathbf{a} = (a_1, \dots, a_n) \in \mathbb{F}_{q^m}^n$ denoted by $\mathrm{Rk}(\mathbf{a})$ is the dimension of the $\mathbb{F}_q$-subspace of $\mathbb{F}_{q^m}$ generated by the components of $\mathbf{a}$, i.e.,

$$ \mathrm{Rk}(\mathbf{a}) \stackrel{\mathrm{def}}{=} \dim\langle a_1, \dots, a_n \rangle_{\mathbb{F}_q}. $$

Gabidulin codes were first constructed by Delsarte as extremal object in Bose-Mesner algebra [10]. Some years later, Gabidulin presented an algebraic theory as well as a polynomial-time decoding algorithm [14]. These codes can be viewed as analogues of Reed-Solomon codes in the rank metric, where polynomials are replaced by linearized polynomials.

**Notation 1** In the whole paper, we will denote by $(a_{i,j})_{1 \le i \le n_r, 1 \le j \le n_c}$ the $n_r \times n_c$ matrix whose entry in row $i$ and column $j$ is equal to $a_{i,j}$ for $i \in \{1..n_r\}$ and $j \in \{1..n_c\}$ or simply $(a_{i,j})$ when the sizes are already clear from the context.

**Definition 1** For integers $k \le n \le m$, let $\mathbf{g} = (g_1, \dots, g_m) \in \mathbb{F}_{q^m}^n$ such that $\mathrm{Rk}(\mathbf{g}) = n$. The $k$-dimensional Gabidulin code with support vector $\mathbf{g}$, denoted $\mathcal{G}_k(\mathbf{g})$, is the $\mathbb{F}_{q^m}$-linear code generated by the matrix $(g_j^{[i-1]})_{1 \le i \le k, 1 \le j \le n}$, where $[i] \stackrel{\mathrm{def}}{=} q^i$.

Finally, the following proposition shows that the dual of a Gabidulin code is a Gabidulin code.
**Proposition 1 ([14])** Let $\mathcal{G}_k(\mathbf{g}) \subset \mathbb{F}_{q^m}^n$, then there exists $\mathbf{h} \in \mathbb{F}_{q^m}^n$ of rank $n$ such that $\mathcal{G}_{n-k}(\mathbf{h}) = \mathcal{G}_k(\mathbf{g})^{\perp}$ for the usual scalar product in $\mathbb{F}_{q^m}$

### 3 Loidreau cryptosystem

The Loidreau scheme was introduced in [19] with $q = 2$ but it can be declined for any prime power $q$. For positive integers $m, n$ and an $\mathbb{F}_q$-vector space $\mathcal{A}$, let $\mathcal{M}_{m,n}(\mathcal{A})$ be the vector space of matrices of size $m \times n$ with entries in $\mathcal{A}$ and let $\text{GL}_n(\mathbb{F}_{q^m})$ be the group of non-singular matrices of size $n$ with entries in $\mathbb{F}_{q^m}$.

#### 3.1 Description of the scheme

The parameters are integers $k \le n \le m$ related to the underlying Gabidulin code as well as $\lambda \in \mathbb{N}$ related to the masking. The value of $\lambda$ is chosen such that $\lambda < \lfloor(n-k)/2\rfloor$ for correctness and $\lambda \ge 3$ to avoid the polynomial attack of [8]. The three standard building blocks of a public encryption scheme are the following:

**KeyGen (1$^{\nu}$)**

1. Construct $\mathcal{G} \subset \mathbb{F}_{q^m}^n$ a $k$-dimensional Gabidulin code.

2. Pick $\mathbf{G} \in \mathcal{M}_{k,n}(\mathbb{F}_{q^m})$ random in the set of full-rank generator matrices for $\mathcal{G}$. A usual way to do it is to choose a matrix under canonical form, say the one given by Definition 1 and then multiply on the left by a randomly chosen matrix in $\text{GL}_k(\mathbb{F}_{q^m})$.

3. Pick $\mathcal{V} \subset \mathbb{F}_{q^m}$ a random $\lambda$-dimensional $\mathbb{F}_q$-subspace of $\mathbb{F}_{q^m}$.

4. Pick $\mathbf{P}$ a random element in $\text{GL}_n(\mathbb{F}_{q^m}) \cap \mathcal{M}_{n,n}(\mathcal{V})$.

5. **return** $\mathbf{G}_{pub} = \mathbf{G}\mathbf{P}^{-1}$ and $\mathbf{sk} = (\mathbf{G}, \mathbf{P})$.

Let $\mathbf{p} \in \mathbb{F}_{q^m}^k$ be the plaintext to be encrypted.

**Encrypt**($\mathbf{p}, \mathbf{G}_{pub}$)

1. Pick $\mathbf{e} \in \mathbb{F}_{q^m}^n$ such that $\text{Rk}(\mathbf{e}) \le \lfloor(n-k)/2\lambda\rfloor$.

2. **return** $\mathbf{c} = \mathbf{p}\mathbf{G}_{pub} + \mathbf{e}$.

**Decrypt**($\mathbf{c}, \mathbf{sk}$)

- **return** $\text{Decode}(\mathbf{cP}, \mathbf{G})$, where $\text{Decode}(*, \mathbf{G})$ stands for any decoding algorithm for a Gabidulin code with generator matrix $\mathbf{G}$ decoding up to the error-correcting capability $\lfloor(n-k)/2\rfloor$.
## 3.2 Security

Let $C_{pub} \subset \mathbb{F}_{q^m}^n$ be the $\mathbb{F}_{q^m}$-linear code of dimension $k$ generated by the public matrix $G_{pub}$. The IND-CPA security of the scheme is related to the difficulty of solving the two following problems:

- Distinguish the code $C_{pub}$ from a random $\mathbb{F}_{q^m}$-linear code with the same parameters.

- Solve a generic instance of the Rank Decoding problem whose parameters are $(m, n, k, t \stackrel{def}{=} \lfloor (n-k)/(2\lambda) \rfloor)$.

In addition to these assumptions, note that LowMS also relies on the Rank Support Learning problem [16].

We address the hardness of the first problem which is used in both [19] and [1]. We even go further since we provide an attack enabling to decrypt. For these schemes, our work also shows that the Gabidulin code itself can be considered as a parameter (meaning that $G$ generating $\mathcal{G}$ is public) without security loss. This leads to a simplification of the key-generation procedure that can be rewritten as

KeyGen()

1. Pick $\mathcal{V} \subset \mathbb{F}_{q^m}$ a random $\lambda$-dimensional $\mathbb{F}_q$-subspace of $\mathbb{F}_{q^m}$.

2. Pick $\mathbf{P}$ randomly in $\text{GL}_n(\mathbb{F}_{q^m}) \cap \mathcal{M}_{n,n}(\mathcal{V})$.

3. return $G_{pub} = \mathbf{pk} = \mathbf{GP}^{-1}$ and $\mathbf{sk} = \mathbf{P}$.

# 4 A constrained linear system for decryption

In this section, we introduce a constrained linear system (Proposition 3) whose solution allows to devise a polynomial time decryption algorithm for the public code $C_{pub}$. Note that this trivially implies that one has designe a distinguisher for the public code. The issue of solving this system will be addressed in the next sections in two different ways.

Let $r \stackrel{def}{=} n-k$. In the following, we overline with a hat data known to an attacker. For instance, let $\hat{\mathbf{H}}_{pub} \in \mathcal{M}_{r,n}(\mathbb{F}_{q^m})$ an arbitrary parity-check matrix for $C_{pub}$ and for $\alpha \in \mathbb{F}_{q^m}$ a normal element, let $\hat{\mathbf{H}}_{norm}$ be the matrix $(\alpha^{[i+j-2]})_{1 \le i \le r, 1 \le j \le m}$. Note that

$$ \hat{\mathcal{A}} \stackrel{def}{=} \{\alpha^{[i]}, i = 0, \dots, m-1\} $$

is a basis of $\mathbb{F}_{q^m}$ over $\mathbb{F}_q$. From Proposition 1, there exists a vector $\mathbf{h} \in \mathbb{F}_{q^m}^n$ such

that $\mathbf{H} \stackrel{def}{=} \begin{pmatrix} \mathbf{h}^{[0]} \\ \vdots \\ \mathbf{h}^{[r-1]} \end{pmatrix} \in \mathcal{M}_{r,n}(\mathbb{F}_{q^m})$ is a parity-check matrix for the Gabidulin
code $\mathcal{G}$. Then, it is easy to see that there exists a unique $\mathbf{S} \in \mathrm{GL}_r(\mathbb{F}_{q^m})$ such that

$$ \mathbf{S}\hat{\mathbf{H}}_{pub} = \mathbf{H}\mathbf{P}^t. \qquad (1) $$

We indeed have $\mathbf{H}\mathbf{P}^t\mathbf{G}_{pub}^t = \mathbf{H}\mathbf{P}^t(\mathbf{P}^t)^{-1}\mathbf{G}^t = \mathbf{H}\mathbf{G}^t = \mathbf{0}$, so that $\mathbf{H}\mathbf{P}^t$ is a parity-check matrix for $C_{pub}$. Finally, any parity-check matrix and, a fortiori, $\hat{\mathbf{H}}_{pub}$, is obtained with a basis transformation induced by a non-singular matrix over $\mathbb{F}_{q^m}$. Another straightforward proposition is

**Proposition 2** Let $\mathbf{H}$ be a parity check matrix for $\mathcal{G}$ under canonical form. There exists a $q$-ary matrix $\mathbf{M} \in \mathcal{M}_{m,n}(\mathbb{F}_q)$ of rank $n$ such that

$$ \mathbf{H} = \hat{\mathbf{H}}_{norm}\mathbf{M}. $$

*Proof.* Let $\mathbf{h} = (h_1, \dots, h_n)$ be the first row of $\mathbf{H}$. We consider the matrix $\mathbf{M}$ whose $i$-th column corresponds to the $m$-dimensional $q$-ary vector formed by the coordinates of $h_i$ in the basis $\hat{\mathcal{A}}$, for $1 \le i \le n$. By construction we have $\mathbf{H} = \hat{\mathbf{H}}_{norm}\mathbf{M}$ and moreover $h_1, \dots, h_n$ are linearly independent over $\mathbb{F}_q$ by construction of Gabidulin codes. This shows that $\mathbf{M}$ has full rank.

Now Equation (1) can be rewritten as

$$ \mathbf{S}\hat{\mathbf{H}}_{pub} = \hat{\mathbf{H}}_{norm}\mathbf{T}, \qquad (2) $$

where the matrix $\mathbf{T} \stackrel{def}{=} \mathbf{M}\mathbf{P}^t$ is full rank in $\mathcal{V}^{m \times n}$ since $\mathbf{M}$ is a $q$-ary matrix of full rank $n$ and since $\mathbf{P} \in \mathrm{GL}_n(\mathcal{V})$. Finally, the following proposition shows that any solution to the constrained linear system described by (2) indeed yields a polynomial-time decryption algorithm.

**Proposition 3** Let $r = n-k$ and let $\hat{\mathbf{H}}_{pub}$ be a parity-check matrix for $C_{pub}$. Let $\alpha \in \mathbb{F}_{q^m}$ be a normal element and let $\hat{\mathbf{H}}_{norm}$ be the matrix $(\alpha^{[i+j-2]})_{1 \le i \le r, 1 \le j \le m}$. From the knowledge of any non-singular matrix $\mathbf{V} \in \mathcal{M}_{r \times r}(\mathbb{F}_{q^m})$ and $\mathbf{W} \in \mathcal{M}_{m \times n}(\mathcal{W})$ of rank $n$ such that

$$ \mathbf{V}\hat{\mathbf{H}}_{pub} = \hat{\mathbf{H}}_{norm}\mathbf{W} \qquad (3) $$

and where $\mathcal{W}$ is $\mathbb{F}_q$-vector subspace of $\mathbb{F}_{q^m}$ of dimension $\le \lambda$, it is possible to decrypt any ciphertext in polynomial time.

*Proof.* Recall that a ciphertext is $\mathbf{c} = \mathbf{p} \cdot \mathbf{G}_{pub} + \mathbf{e} \in \mathbb{F}_{q^m}^n$, where $\mathrm{Rk}(\mathbf{e}) = \lfloor(n-k)/(2\lambda)\rfloor$. Thus $\hat{\mathbf{H}}_{pub}\mathbf{c}^t = \hat{\mathbf{H}}_{pub}\mathbf{e}^t$ and

$$ \mathbf{V}\hat{\mathbf{H}}_{pub}\mathbf{e}^t = \hat{\mathbf{H}}_{norm}\underbrace{\mathbf{W}\mathbf{e}^t}_{\mathbf{e}^t}. $$

Since $\mathcal{W}$ has dimension $\le \lambda$, this implies that and $\mathrm{Rk}(\mathbf{e}') \le \lambda\mathrm{Rk}(\mathbf{e}) \le \lfloor(n-k)/2\rfloor$. Therefore by decoding in the public Gabidulin code with parity-check matrix $\hat{\mathbf{H}}_{norm}$, one recovers $\mathbf{e}'^t = \mathbf{W}\mathbf{e}^t$. Since $\mathbf{W}$ has rank $n \le m$, $\mathbf{e} \mapsto \mathbf{W}^t\mathbf{e}$ is one-to-one and $\mathbf{e}$ can be uniquely recovered. The vector $\mathbf{p}$ such that $\mathbf{p} \cdot \mathbf{G}_{pub} = \mathbf{c} - \mathbf{e}$ can also be uniquely recovered. $\square$
To conclude this section, note that a first naive solving approach would be to enumerate all solutions $(V, W) \in \mathcal{M}_{r \times r}(\mathbb{F}_{q^m}) \times \mathcal{M}_{m \times n}(\mathbb{F}_{q^m})$ to (3) and to test if they satisfy the constraint, i.e., the $W$ matrix has its entries in a small dimensional $\mathbb{F}_q$-vector subspace of $\mathbb{F}_{q^m}$. Even if one takes into account the fact that there may be multiple possibilities, this effort lies beyond the capacities of any computer even for moderate parameters. Indeed, a first difficulty is that the solution space to (3) is an $\mathbb{F}_{q^m}$-vector space of dimension at least $r^2 + (m - r)n$ without the imposed condition.

# 5 Combinatorial approach

A first idea to take advantage of this extra information is to enumerate candidate bases $\mu \in \mathbb{F}_{q^m}^\lambda$ for the secret vector space $V$. Any such candidate is then completed into a basis of $\mathbb{F}_{q^m}$ in which we express the coefficients of $V$ and $W$ in order to write down the linear system (3) over $\mathbb{F}_q$. We assume that each entry in $W$ belongs to the $\mathbb{F}_q$-vector space spanned by $\mu$ and thus we introduce only $\lambda mn$ unknowns over $\mathbb{F}_q$ instead of $m^2n$ for this matrix. Since we typically have $rmn \gg \lambda mn + mr^2$, this initial guess can be tested by solving the resulting linear equations over $\mathbb{F}_q$ to check if they have a non-zero solution. As is usual for this type of approach, the total cost contains two factors:

- an exponential one coming from enumerating the bases;

- a polynomial one which corresponds to the linear system solving over $\mathbb{F}_q$.

**Proposed algorithm.** We can in fact obtain a better exponential factor by relying on the same techniques as used in combinatorial attacks on the Rank Decoding problem [21,17,2]. The rationale is that it is enough to know (a basis for) a $\gamma$-dimensional vector space $U$ which contains $V$ for $\gamma \ge \lambda$ to apply the same algorithm, provided that $\gamma$ is not too large. The advantage is that it is always easier to find such a $U$ than to guess a basis of $V$ directly, the extreme case being $\gamma = m$ for which we succeed with probability 1. Here, we even note that a vector space $U$ which contains an arbitrary multiple $xV$ for $x \in \mathbb{F}_{q^m}^*$ instead of simply $V$ is enough for our purposes. This is because any pair $(xV, xW)$ is a solution to the constrained linear system. The following Proposition 4 gives the condition on $\gamma$ for our attack to succeed.

**Proposition 4** Assume that $\gamma \ge \lambda \in \mathbb{N}$ is such that

$$rn \ge \gamma n + r^2. \quad (4)$$

If $\nu \in \mathbb{F}_{q^m}^\gamma$ is a basis for a vector space $U$ which contains a multiple $xV$ for $x \in \mathbb{F}_{q^m}^*$, the linear system over $\mathbb{F}_q$ derived from (3) by writing the coefficients of the secret matrix $W$ in the basis $\nu$ is expected to have a solution space of dimension 1. If $\nu$ does not correspond to such a basis, this linear system will not have a non-zero solution with overwhelming probability.

From this proposition, we can then use the same algorithm as sketched at the beginning of Section 5 with $\gamma$ instead of $\lambda$ provided that $\gamma \le r(1 - r/n)$.
**Estimated cost.** The exponential factor of this approach is given by the inverse of the probability that a fixed subspace $\mathcal{U}$ of dimension $\gamma$ contains a subspace of the form $x\mathcal{V}$ for some $x \in \mathbb{F}_{q^m}^*$. According to [2, B.], it can be estimated by $q^{m-\lambda(m-\gamma)} = q^{-(\lambda-1)m+\lambda\gamma}$. We assume that the optimal complexity corresponds to the optimal exponential factor and thus we consider the highest possible value for $\gamma$. By Equation (4), this leads to choose $\gamma \stackrel{\text{def}}{=} \lfloor r(1-r/n) \rfloor$.

The linear system solving step can be performed by applying Gaussian elimination on a matrix of size $rmn \times (\gamma n + r^2)m$ over $\mathbb{F}_q$. The corresponding cost in $\mathbb{F}_q$-operations can be estimated by $\mathcal{O}((\gamma n + r^2)m)^\omega$, where $\omega$ is the linear algebra constant. However, checking that a linear system is consistent does not require to compute a row echelon form. We can actually apply the Wiedemann algorithm [9], which may offer an advantage since the input matrix is sparse. Indeed, equations have weight $m(r+\gamma)$ but they contain $m(r^2+\gamma n) \gg m(r+\gamma)$ unknowns. In particular, we lower bound the complexity of linear algebra by considering the cost of computing the kernel of a sparse square matrix of size $m(\gamma n + r^2)$ corresponding to the number of unknowns with a number of non-zero coefficients roughly equal to $m^2(r+\gamma)(\gamma n + r^2)$. An estimation of this lower bound is

$$m^3(r + \gamma)(\gamma n + r^2)^2 > m^3 r^5$$

$q$-ary operations. Recalling that $r = n - k$ and by introducing the code rate $R \stackrel{\text{def}}{=} k/n$, a lower bound of the overall complexity of this precise attack is then given by

$$W_{\text{Spec\_Inf}} = m^3(n-k)^5 q^{(\lambda-1)m-\lambda\lfloor n(1-R)R \rfloor}. \quad (5)$$

**Application to some parameters.** Finally, we instantiate our bound with the parameters of the WCC 2022 abstract and the ones of LowMS [1]. We believe that the comparison is fair since they have been obtained from the content of the abstract. In Table 1, column *Lower bound* contains the value of the binary logarithm of the cost of Equation (5). Our results always improve the cost of the best structural attack. If it becomes below the one of attacks on RD, this might lead to re-evaluate parameters in [19] and [1].

<table><caption>**Table 1.** Cost estimate on former parameters.</caption><thead><tr><th>(<i>m</i>, <i>n</i>, <i>k</i>, <i>λ</i>)</th><th>Security</th><th>Source</th><th>Lower bound</th><th>Former</th></tr></thead><tbody><tr><td>(128, 128, 20, 3)</td><td>128</td><td>WCC 2022</td><td>263</td><td>311</td></tr><tr><td>(128, 128, 44, 3)</td><td>128</td><td>WCC 2022</td><td>225</td><td>308</td></tr><tr><td>(59, 50, 25, 3)</td><td>128</td><td>LowMS</td><td><b>123</b></td><td>158</td></tr><tr><td>(67, 66, 33, 4)</td><td>128</td><td>LowMS</td><td>180</td><td>244</td></tr><tr><td>(83, 74, 37, 3)</td><td>192</td><td>LowMS</td><td><b>157</b></td><td>211</td></tr><tr><td>(79, 78, 39, 4)</td><td>192</td><td>LowMS</td><td>206</td><td>282</td></tr></tbody></table>
Note however that we do not claim that the lower bound is on all possible algorithms which would solve the same problem. The lower bound in our case only deals with the linear algebra part when using Wiedemann’s algorithm. It is a lower bound relatively to the state of the art of research in this field.

## 6 A bilinear system

Instead of guessing a basis for $V$ or for a vector space which contains it as in Section 5, our second approach consists in solving a bilinear system over $\mathbb{F}_q$ (System 1). These former quantities attached to $V$ still appear in the system as an unknown block of variables but we will not fix them in the first place.

Let $\hat{\mathcal{B}}$ denote an arbitrary basis of $\mathbb{F}_{q^m}$ over $\mathbb{F}_q$. For an element $a \in \mathbb{F}_{q^m}$, we consider $\vec{a}$ the $m$-dimensional vector of its coordinates over $\hat{\mathcal{B}}$, so that $\hat{\mathcal{B}}\vec{a} = a$. For $\mu \in \mathbb{F}_{q^m}$, we also define $\mathbf{M}_{\mu} \in \mathcal{M}_{m \times m}(\mathbb{F}_q)$ the matrix of the multiplication by $\mu$ in the basis $\hat{\mathcal{B}}$. This matrix is such that

$$ \forall a, b \in \mathbb{F}_{q^m}, b = \mu a, \text{ then } \vec{b} = \mathbf{M}_{\mu} \vec{a}. $$

The claimed bilinear system is as follows:

**System 1** Let $\hat{\mathbf{H}}_{pub} = (\hat{h}_{ij})$ and let $\hat{\mathbf{H}}_{norm} = (\alpha^{[i+j-2]})$. We consider the bilinear system over $\mathbb{F}_q$ in the non-zero unknowns $\vec{v}_{iu}$, $b_{ij}^{(\ell)}$ and linearly independent $\vec{\mu}_{\ell} \in \mathbb{F}_q^m$, whose equations are given by

$$ \forall \begin{cases} i \in \{1..r\} \\ j \in \{1..n\} \end{cases}, \quad \sum_{u=1}^{r} \mathbf{M}_{\hat{h}_{uj}} \vec{v}_{iu} = \sum_{u=1,\ell=1}^{m,\lambda} b_{uj}^{(\ell)} \mathbf{M}_{\alpha^{[i+u-2]}} \vec{\mu}_{\ell}. \quad (6) $$

**System 1** contains $mrn$ affine equations over $\mathbb{F}_q$. The linear parts involve $mr^2$ variables $\vec{v}_{iu}$ while the bilinear parts involve $\lambda mn + \lambda m$ variables $b_{ij}^{(\ell)}$ and $\vec{\mu}_{\ell}$ respectively. Proposition 5 states that the solutions to this system are actually equivalent to the ones of the constrained linear equations (3).

**Proposition 5** Let $\tilde{\mathbf{V}} = (v_{ij}) \in \mathcal{M}_{r \times r}(\mathbb{F}_{q^m})$ and $\tilde{\mathbf{W}} = (w_{ij}) \in \mathcal{M}_{m \times n}(\mathbb{F}_{q^m})$ which satisfy the constrained linear equations (3) and let $\mathcal{W}$ a$^4$ $\lambda$-dimensional subspace of $\mathbb{F}_{q^m}$ which contains the entries of $\tilde{\mathbf{W}}$. Let $(\mu_1, \dots, \mu_\lambda) \in \mathbb{F}_{q^m}^\lambda$ be a basis for $\mathcal{W}$ and

$$ w_{ij} \stackrel{\text{def}}{=} \sum_{\ell=1}^{\lambda} b_{ij}^{(\ell)} \mu_{\ell} \quad (7) $$

be the unique decomposition of $w_{ij}$ in this basis. Then $\vec{v}_{iu} \in \mathbb{F}_q^m$, $b_{ij}^{(\ell)}$ and $\vec{\mu}_{\ell}$ are a solution to System 1. Conversely, any solution $\vec{v}_{iu}$, $b_{ij}^{(\ell)}$, $\vec{\mu}_{\ell}$ to System 1 gives a pair of matrices $\tilde{\mathbf{V}} = (v_{ij})$, $\tilde{\mathbf{W}} = (w_{ij})$ solution to the constrained linear equations (3), where $w_{ij}$ is defined by Equation (7).

<footnote n="4">⁴ concretely, “the”</footnote>
If $(V, W)$ stands for the genuine couple of matrices which is implicit from the description of the scheme, we have already mentioned that any $(\tilde{V}, \tilde{W}) \stackrel{\text{def}}{=} (xV, xW)$ for $x \in \mathbb{F}_{q^m}^*$ allows to decrypt. Concretely, to reduce the number of solutions to System 1, we will thus:

- fix $\mu_1$ to 1 and choose a basis $\hat{B}$ such that $\hat{b}_1 = 1$;

- target a basis in systematic form, i.e.,

$$ (1, \mu_2, \dots, \mu_\lambda)^\top \stackrel{\text{def}}{=} \begin{pmatrix} \mathbf{0}_{1 \times (m-\lambda)} \\ \mathbf{I}_\lambda \\ \mathbf{R}' \end{pmatrix} \hat{B}^\top, \qquad (8) $$

where $\mathbf{R}' \in \mathcal{M}_{(\lambda-1) \times (m-\lambda)}(\mathbb{F}_q)$. We cannot always guarantee to have a solution in this way but the success probability is constant.

Note that similar strategies to fix variables had already been suggested in previous works, see for instance [7, §3.4] or [21, §3.1].

**Solving by Gröbner bases.** To solve System 1, one may be tempted to use Gröbner basis techniques [11,12,13]. However, our practical experiments for this method were not conclusive. A reason is that there is a great imbalance between the two blocks of variables $\vec{\mu}_\ell$ and $b_{ij}^{(\ell)}$ since $(\lambda-1)(m-\lambda) \ll mn\lambda$. This also explains why it was quite natural in Section 5 to proceed by enumeration on the smallest block $\vec{\mu}_\ell$ (corresponding to an unknown basis for $V$) in order to obtain linear equations.

# 7 Tools to analyze System 1

Even if the Gröbner basis approach seems infeasible, this section gives some background to partially explain the early steps of such an algorithm. More specifically, in Section 8, we will characterize the first degree fall polynomials (see Definition 2) which arise in the computation.

Gröbner basis solvers [11,12,13] had already been analyzed by [13] in the context of generic bilinear systems. However, in our case, we need to use the fact that System 1 admits a much stronger structure than being merely bilinear. It turns out that its analysis is much closer to the one performed in [4,23] on bilinear modelings of MinRank and of the Rank Decoding problem. Indeed, a common feature in such systems is that the equations can be viewed as the entries of a matrix $M = AXY$, where $A$ is a matrix of scalars and where $X$ and $Y$ are matrices of unknowns $x$ and $y$ respectively. It is easy to see that our equations exhibit a similar shape. Using the notation from System 1, we can indeed write each column $w_j = (w_{1,j}, \dots, w_{m,j}) \in \mathbb{F}_{q^m}^*$ of the unknown $W$ as $w_j^\top = C_j(\mu_1, \dots, \mu_\lambda)^\top = C_j \mathbf{R} \hat{B}^\top$, where $C_j \stackrel{\text{def}}{=} (b_{i,j}^{(\ell)})_{1 \le i \le m, 1 \le \ell \le \lambda}$ and where the rows of $\mathbf{R} \in \mathcal{M}_{\lambda \times m}(\mathbb{F}_q)$ are the $\vec{\mu}_\ell$'s for $1 \le \ell \le \lambda$. We then obtain
**System 0** For $j \in \{1..n\}$, let $\hat{h}_j \in \mathbb{F}_{q^m}^r$ denote the j-th column in $\hat{\mathbf{H}}_{pub}$. There are r bilinear equations in the entries of $\tilde{\mathbf{V}}$, $\mathbf{R}$ and $\mathbf{C}_j$ from the equality

$$ \tilde{\mathbf{V}}\hat{\mathbf{h}}_j^\mathrm{T} = \hat{\mathbf{H}}_{\mathrm{norm}}\mathbf{C}_j\mathbf{R}\hat{\mathbf{B}}^\mathrm{T}. \qquad (9) $$

By considering all columns, we obtain an affine bilinear system with

- $rn$ equations over $\mathbb{F}_{q^m}$.

- $r^2$ unknowns $v_{ij}$ over $\mathbb{F}_{q^m}$ and $\lambda mn + \lambda m$ unknowns over $\mathbb{F}_q$.

Note that **System 1** captures exactly the same information as the system over $\mathbb{F}_q$ obtained from **System 0** by taking as unknowns the $v_{iu}$'s instead of the $v_{ij}$'s and then by projecting over the base field. We may adopt the latter for the theoretical analysis since it is more convenient.

## 7.1 Algebraic background

Let us start with some necessary facts on Gröbner bases techniques applied to bilinear systems.

**Syzygies and degree falls.** For a polynomial sequence $\mathcal{F} = (f_1, \dots, f_M)$, a syzygy is a polynomial combination $\sum_{i=1}^M g_i f_i = 0$. Its degree is defined by $\max_{i=1}^M (\deg(g_i f_i))$. In our systems, recall that any polynomial is of the form $f_i = b_i + l_i$ where $b_i$ is bilinear and $l_i$ is linear. In particular, a syzygy $\sum_{i=1}^M g_i b_i = 0$ of degree $d$ for $(b_1, \dots, b_M)$ typically yields an equation $\sum_{i=1}^m g_i f_i = \sum_{i=1}^M g_i l_i = 0$ of degree $d-1$ in the ideal. This is a particular case of

**Definition 2 (Degree fall polynomial)** A degree fall polynomial for a sequence $\mathcal{F} = (f_1, \dots, f_M)$ is a non-zero polynomial combination $\sum_{i=1}^M g_i f_i$ whose degree $\delta$ is strictly less than $d \stackrel{\mathrm{def}}{=} \max_{i=1}^M (\deg(g_i f_i))$. We may also refer to it as a degree fall from degree $d$ to degree $\delta$.

Such an equation will be meaningful if and only if it is not a linear combination between previously considered equations of degree $\le d-1$. Some actually prefer to include this extra constraint already in Definition 2. Degree fall polynomials for affine systems play a similar role to that of syzygies for homogeneous equations. Their study is thus instrumental to understand the complexity of solving such affine equations.

**Bilinear systems** [13]. Let $\mathcal{B} = (b_1, \dots, b_M) \subset \mathbb{F}[\mathbf{x}, \mathbf{y}]$ be the homogeneous bilinear sequence in two blocks of variables $\mathbf{x}$ and $\mathbf{y}$ over a field $\mathbb{F}$ which contains the degree 2 parts of an affine bilinear sequence $\mathcal{F}$. As we have just said, degree fall polynomials for $\mathcal{F}$ are directly related to syzygies for $\mathcal{B}$. Let us now consider the Jacobian matrices which are defined by
$$Jac_x(S) \stackrel{\text{def}}{=} \left( \frac{\partial b_i}{\partial x_j} \right)_{1 \le i \le M, 1 \le j \le n_x}$$

and

$$Jac_y(S) \stackrel{\text{def}}{=} \left( \frac{\partial b_i}{\partial y_j} \right)_{1 \le i \le M, 1 \le j \le n_y}.$$

Their entries are linear forms in $\mathbb{F}[y]$ and $\mathbb{F}[x]$ respectively. The study of these Jacobians is motivated by the following Lemma 1, which states that generic syzygies for $S$ are provided by vectors in the left kernel of these matrices.

**Lemma 1** Let $S \stackrel{\text{def}}{=} (b_1, \dots, b_M) \subset \mathbb{F}[x, y]$ be a homogeneous bilinear sequence and let $G \stackrel{\text{def}}{=} (g_1, \dots, g_M) \subset \mathbb{F}[y]^M$ be a polynomial sequence. We have $\sum_{i=1}^M g_i b_i = 0$ if and only if $G$ belongs to the left kernel of $Jac_x(S)$.

*Proof.* Let $G = (g_1, \dots, g_M)$ be an arbitrary polynomial sequence. Since we have

$$GJac_x(S)x^T = \sum_{i=1}^{M} g_i b_i,$$

we obtain a syzygy from any kernel vector of $Jac_x(S)$. The converse statement is only valid for $G \subset \mathbb{F}[y]^M$. For such a vector of polynomials, the product by $Jac_x(S)$ is still a row vector of elements in $\mathbb{F}[y]$. The only possibility for it to be 0 when multiplied by $x^T$ is that it is already 0, i.e., $G \in \ker(Jac_x(S))$. $\square$

The following Lemma 2 gives kernel vectors for these Jacobian matrices regardless of their structure.

**Lemma 2 (Lemma 3.1 in [13])** Let $M \in \mathcal{M}_{M \times t}(\mathbb{F}[y])$ be a matrix whose entries are linear forms with $t < M$. Let

$$V_J \stackrel{\text{def}}{=} (\dots, \underbrace{0}_{j \notin J}, \dots, \underbrace{(-1)^{\ell+1} |M|_{J \setminus \{j_\ell, \dots, j_M\}}}_{j=j_\ell}, \dots),$$

where $J = \{j_1 < \dots < j_{t+1}\} \subset \{1..M\}$. These vectors are such that $V_J M = 0$.

Generically, the vectors $V_J$ generate the left kernel of such a matrix $M$, see for instance [13, Conjecture 4.1]. Also, for a bilinear random $S$, the entries of the matrix $Jac_x(S)$ are random linear forms in $\mathbb{F}[y]$. Lemma 2 was thus used in [13] to have a complete description of its left kernel. Based on this result, they show that the degree of regularity of a generic bilinear system is such that $d_{\text{reg}} \le \min(n_x + 1, n_y + 1)$.

However, the bilinear equations relevant to us are not generic and we will have to analyze the structure of the Jacobians.
**A useful lemma.** Consider a matrix equation $M = AXY \in \mathcal{M}_{p \times n}(\mathbb{F}[x, y])$ as in the beginning of this section, where $A \in \mathcal{M}_{p \times m}(\mathbb{F})$ is a matrix of scalars and where $X \in \mathcal{M}_{m \times r}(\mathbb{F}[x])$ and $Y \in \mathcal{M}_{r \times n}(\mathbb{F}[y])$ are matrices of unknowns $x$ and $y$ respectively. Let us define the row vector $(M_{\{1\},*} \dots M_{\{m\},*})$ formed by the concatenation of the rows of $M$ and similarly $\mathrm{col}(M) \stackrel{\mathrm{def}}{=} \mathrm{row}(M^\mathrm{T})$. Then we have the following lemma

**Lemma 3** The Jacobian matrix of a system $AXY = 0_{p \times n}$ with respect to the $x$ variables is given by

$$Jac_{row}(X)(row(AXY)) = A \otimes Y^T \in \mathcal{M}_{np \times mr}(\mathbb{F}[y]), \\ Jac_{col}(X)(col(AXY)) = Y^T \otimes A \in \mathcal{M}_{np \times mr}(\mathbb{F}[y]).$$

*Proof.* See [4, Lemma 1]. □

## 7.2 Understanding the projection over $\mathbb{F}_q$

In addition to the matrix product structure, another particularity comes from the extension field. Indeed, recall that **System 1** can be seen as the projection over $\mathbb{F}_q$ of **System 0** whose equations have coefficients in $\mathbb{F}_{q^m}$ but where the variables involved in the bilinear parts belong to $\mathbb{F}_q$. In that respect, this system is obtained in the exact same manner as in [3,4,6] which aim at solving the Rank Decoding Problem and the Rank Support Learning Problem.

In the case of [3,4,6], the analysis of the full system over $\mathbb{F}_q$ can be boiled down to the one of the initial system over $\mathbb{F}_{q^m}$. On our side, however, the situation is less simple. For instance, it is not sufficient to analyze **System 0** to understand the computation on **System 1** over $\mathbb{F}_q$. This might be due to the following simple fact: by choosing $\hat{\mathcal{B}} = \mathcal{A} = \{1, \alpha^{[1]}, \dots, \alpha^{[m-1]}\}$ to express **System 0**, we actually recover the first row of $\hat{\mathbf{H}}_{norm}$. This gives another interesting property which was not present in [3,4,6].

As explained after the definition of **System 0**, projecting this system yields equations over $\mathbb{F}_q$ which generate the same system as **System 1**. Let us denote by $\{b_1, \dots, b_m\}$ the set of $m$ equations over $\mathbb{F}_q$ obtained by projecting the bilinear part $b$ of an equation of **System 0**. Also, let us extend the Frobenius map to polynomials by reducing modulo the field equations of the small field since all variables belong to $\mathbb{F}_q$, namely $b^{[\ell]} \stackrel{\mathrm{def}}{=} b^{q^\ell} \mod \langle x_i^q - x_i \rangle_i$. For a matrix $M = (m_{ij})$ over $\mathbb{F}_{q^m}$ (or over a polynomial ring with base field $\mathbb{F}_{q^m}$), we also denote by $M^{[\ell]}$ the matrix $(m_{ij}^{[\ell]})$. Finally, in our analysis, we will use the fact that the algebraic properties<fnref n="5" /> of both sequences $(b_1, \dots, b_m)$ and $(b, \dots, b^{[m-1]})$ are the same. In particular, it will be relevant to consider the following **System 2** which is equivalent to **System 1**.

<footnote n="5">⁵ syzygies, etc.</footnote>
**System 2** For $j \in \{1..n\}$, let $\hat{h}_j \in \mathbb{F}_{q^m}^r$ denote the j-th column in $\hat{\mathbf{H}}_{pub}$. For any $0 \le \ell \le m-1$, we consider the r equations obtained by applying the Frobenius $\ell$ times on Equation (9). They are given by

$$V^{[\ell]} (\hat{h}_j^{[\ell]})^{\top} = \hat{\mathbf{H}}_{norm}^{[\ell]} C_j \mathbf{R} (\hat{\mathbf{B}}^{[\ell]})^{\top}. \quad (10)$$

We stress that **System 2** has essentially a theoretical value. In particular, it would not be suitable to solve it by using naive Gröbner basis algorithms since the equations have very high degree in the $v_{i,j}$ variables.

# 8 Degree fall polynomials from Jacobians

This final section aims at studying the Jacobians associated to the bilinear parts of our equations. We will show in Lemma 4 and Lemma 5 that their kernels provide two types syzygies in degree $\lambda + 2$, hence degree fall polynomials of degree $\lambda + 1$ for the original affine equations. Moreover, our experiments suggest that these are the only ones at this degree and that these are the first, i.e., no one appear at a lower degree.

Interestingly enough, we do not need to wait the degree $\lambda+2$ step of a Gröbner basis algorithm on **System 0** or **System 1** for a graded order to obtain these polynomials. They can indeed be pre-computed as maximal minors of public matrices of linear forms. In that respect, the situation is quite similar to the one of algebraic attacks on the Rank Decoding problem [21,4,6,5]. For instance, the so-called MaxMinors equations introduced in [4] were originally obtained as degree fall polynomials for the former bilinear modeling of Ourivski-Johansson [21] but they can also be computed directly.

For the sake of simplicity, we give the results for the non-specialized version of our systems. They can be easily adapted if we fix $\mu_1$ to 1 and if we choose a matrix $\mathbf{R}$ in systematic form as presented above.

## 8.1 Jacobian with respect to the $\mathbf{R}$ variables

We start from the Jacobian matrices with respect to the block of $\mathbf{R}$ variables. We will see that their structure is similar to the one encountered in [4, §5.1]. As in their work, we also observed that all degree falls over $\mathbb{F}_q$ from these matrices were obtained by projecting over $\mathbb{F}_q$ degree fall polynomials whose coefficients are in $\mathbb{F}_{q^m}$. This means that we can focus on **System 0** rather than on **System 1** for this part of the analysis, the situation being different in Section 8.2.

If we restrict ourselves to the bilinear parts in **System 0**, a direct application of Lemma 3 for $1 \le j \le n$ with $\mathbf{X} \stackrel{def}{=} \mathbf{R}$, $\mathbf{A} \stackrel{def}{=} \hat{\mathbf{H}}_{norm}C_j$ and $\mathbf{Y} \stackrel{def}{=} \hat{\mathbf{B}}^{\top}$ yields

$$\mathrm{Jac}_{\mathrm{row}(\mathbf{R})}(\mathrm{row}(\hat{\mathbf{H}}_{\mathrm{norm}}C_j \mathbf{R} \hat{\mathbf{B}}^{\top})) = \hat{\mathbf{H}}_{\mathrm{norm}}C_j \otimes \hat{\mathbf{B}}. \quad (11)$$
The full system can also be viewed as the following matrix product

$$ (I_n \otimes \hat{\mathbf{H}}_{\text{norm}}) \begin{pmatrix} C_1 \\ \vdots \\ C_n \end{pmatrix} R \hat{\mathbf{B}}^{\top}, $$

and thus we obtain in the same manner

$$ \text{Jac}_{\text{row}(\mathbf{R})} \left( (I_n \otimes \hat{\mathbf{H}}_{\text{norm}}) \begin{pmatrix} C_1 \\ \vdots \\ C_n \end{pmatrix} R \hat{\mathbf{B}}^{\top} \right) = \begin{pmatrix} \hat{\mathbf{H}}_{\text{norm}} C_1 \\ \vdots \\ \hat{\mathbf{H}}_{\text{norm}} C_n \end{pmatrix} \otimes \hat{\mathbf{B}}. \quad (12) $$

Recall from Lemma 1 that the kernel of such Jacobians provides syzygies for the bilinear parts whose coefficients are polynomials in the $C_j$ variables. In our case, we can obtain

**Lemma 4** In System 0, there are at least $\binom{nr}{\lambda+1}$ degree falls from degree $\lambda+2$ to $\lambda+1$. Indeed, some of them are already given by the maximal minors of the matrix

$$ \mathcal{M} \stackrel{\text{def}}{=} \begin{pmatrix} \tilde{V} \hat{h}_1^\top & \hat{\mathbf{H}}_{\text{norm}} C_1 \\ \vdots & \vdots \\ \tilde{V} \hat{h}_n^\top & \hat{\mathbf{H}}_{\text{norm}} C_n \end{pmatrix}. \quad (13) $$

Among these equations, we may find in particular the maximal minors of the matrix

$$ \mathcal{M}_j \stackrel{\text{def}}{=} \mathcal{M}_{\{1+r(j-1)\dots rj\},*} = (\tilde{V} \hat{h}_j^\top \hat{\mathbf{H}}_{\text{norm}} C_j), \quad (14) $$

for $1 \le j \le n$.

Even before giving the proof of Lemma 4, it is easy to see from Equation (9) that all $\mathcal{M}_j$ matrices are not full-rank (a fortiori, $\mathcal{M}$) if and only if $(\tilde{V}, C_1, \dots, C_n)$ are components of a solution to System 0.

*Proof.* (Analogous to [4]). We do the proof for a single matrix $\mathcal{M}_j$. Using Equation (11), it is sufficient to look at the left kernel of $\hat{\mathbf{H}}_{\text{norm}} C_j$. We then compute the kernel vectors $V_J$ of Lemma 2 for this matrix of linear forms, namely

$$ V_J \stackrel{\text{def}}{=} \left( \underbrace{0}_{j \notin J}, \dots, \underbrace{(-1)^{\ell+1} |\hat{\mathbf{H}}_{\text{norm}} C_j|}_{j=\ell \in J}, \dots \right), \quad \# J = \lambda+1, \ J \subset \{1..r\}. $$
The degree falls are then obtained by multiplying these vectors by the linear parts of the equations, i.e. $(V_J) \cdot \tilde{V} \tilde{h}_j^T$. Finally, the latter actually coincides with the maximal minor $|M_j|_{J,*}$ using Laplace expansion along the first column. The reasoning is similar for $\mathcal{M}$ if we replace Equation (11) by Equation (12). $\square$

**Bilinear structure.** The degree fall polynomials given by Lemma 4 have degree $\lambda + 1$. Moreover, Laplace expansion along the first column of $\mathcal{M}$ in Equation (13) shows that these equations are *bilinear* in the entries of $\tilde{V}$ (which belong to $\mathbb{F}_{q^m}$) and in the maximal minors of the matrix

$$D \stackrel{\text{def}}{=} \begin{pmatrix} C_1 \\ \vdots \\ C_n \end{pmatrix},$$

whose coefficients are in $\mathbb{F}_q$. Similarly, the maximal minors of $M_j$ are simply bilinear in the entries of $\tilde{V}$ and in the $\binom{m}{\lambda}$ maximal minors of $C_j$. Such a structure had already been encountered in the bilinear systems of [5,6] to attack the Rank Decoding Problem and MinRank. In particular, note that the newly introduced bilinear modeling of [5] ([5, Modeling 4]) has exactly the same shape as it involves a block of *linear variables* over the extension field $\mathbb{F}_{q^m}$ and a block of *minor variables* over $\mathbb{F}_q$.

**Projection over $\mathbb{F}_q$.** In System 1, we observed $m\binom{nr}{\lambda+1}$ (linearly independent) degree falls from degree $\lambda + 2$ to degree $\lambda + 1$ which involve these variables$^6$ in our experiments. Clearly, they should coincide with the projection over $\mathbb{F}_q$ of the degree fall polynomials described in Lemma 4 for System 0. To project the equations, note that we also have to express the entries of $\tilde{V}$ over $\mathbb{F}_q$. This yields $r^2m$ variables $v_{iu}$ and thus $r^2m\binom{mn}{\lambda}$ degree 2 monomials among these degree fall polynomials (but only $r^2m\binom{m}{\lambda}$ if we restrict ourselves to one matrix $C_j$).

## 8.2 Jacobian with respect to the $C_j$ variables

Contrary to the systems of [4,5,6] to solve the Rank Decoding Problem, a specificity of System 1 is that the Jacobian with respect to the other block of variables also yields degree fall polynomials of low degree, for instance $\lambda + 1$. One cannot grasp them by studying System 0 only.

**Absence of degree falls for System 0.** First, let us explain why we do not expect degree fall polynomials of small degree coming from this Jacobian for System 0. Note that the set $S$ of bilinear parts of the equations from this system can be written as $S \stackrel{\text{def}}{=} \bigcup_{j=1}^n S_j$, where the polynomials in $S_j$ are defined

<footnote>$^6$ Section 8.2 will give another type of degree falls in the same degree</footnote>
as the entries of the matrix $\hat{\mathbf{H}}_{\text{norm}} C_j R \hat{\mathbf{B}}^{\top}$ at the right hand side of Equation (9). The $R \hat{\mathbf{B}}^{\top}$ part being independent of $j$, we already obtain $\text{Jac}_{\text{row}(C_j)}(\text{row}(S_j)) = \text{Jac}_{\text{row}(C_1)}(\text{row}(S_1))$ for any $j$ and thus

$$ \text{Jac}_{\text{row}(C)}(\text{row}(S)) = I_n \otimes \text{Jac}_{\text{row}(C_1)}(\text{row}(S_1)). $$

Then, to compute $\text{Jac}_{\text{row}(C_1)}(\text{row}(S_1))$, we apply Lemma 3 once again this time with $\mathbf{X} \stackrel{\text{def}}{=} \hat{\mathbf{H}}_{\text{norm}}$, $\mathbf{A} \stackrel{\text{def}}{=} C_1$ and $\mathbf{Y} \stackrel{\text{def}}{=} R \hat{\mathbf{B}}^{\top}$. This yields

$$ \text{Jac}_{\text{row}(C_1)}(\text{row}(S_1)) = \hat{\mathbf{H}}_{\text{norm}} \otimes \hat{\mathbf{B}} \mathbf{R}^{\top}. \quad (15) $$

This matrix is of size $r \times m\lambda$ and its entries are linear forms in the $\mathbf{R}$ variables. However, we cannot apply Lemma 2 since $r < m\lambda$. We expect a trivial left kernel for this matrix.

**Additional degree falls for System 1.** We analyze the situation over $\mathbb{F}_q$ by studying the **System 2** introduced in Section 7.2, which contains the same information as **System 1**. From now on we fix $\hat{\mathbf{B}} = \mathcal{A}$. As in the previous section, we can clearly reason in a similar way for all indexes $1 \le j \le n$. For $1 \le j \le n$ and $0 \le \ell \le m-1$, let us consider Equation (10) and for $1 \le u \le r$, let us denote by $g_{u,\ell,j}$ the bilinear polynomial

$$ g_{u,\ell,j} \stackrel{\text{def}}{=} (\hat{\mathbf{H}}_{\text{norm}}^{[\ell]})_{u,*} C_j \mathbf{R} (\mathcal{A}^{[\ell]})^{\top} = (\mathcal{A}^{[\ell+u-1]}) C_j \mathbf{R} (\mathcal{A}^{[\ell]})^{\top}. $$

We also keep track of the corresponding linear part $L_{u,\ell,j} \stackrel{\text{def}}{=} V_{u,*}^{[\ell]} (\widehat{\mathbf{h}}_j^{[\ell]})^{\top}$, so that the whole equation reads $g_{u,\ell,j} - L_{u,\ell,j} = 0$. We then group the equations according to the value of $v \stackrel{\text{def}}{=} u+\ell-1 \bmod m$. We obtain the following equality, where all $\ell$ indexes are modulo $m$,

$$ \begin{aligned} (L_{1,v,j} L_{2,v-1,j} \dots L_{r,v-r+1,j}) &= (g_{1,v,j} \dots g_{r,v-r+1,j}) \\ \widehat{\mathbf{h}}_j^{[\ell]} (\mathbf{V}^{[\ell]})^{\top} &= \mathcal{A}^{[v]} C_j \mathbf{R} \left( (\mathcal{A}^{[v]})^{\top} \vdots (\mathcal{A}^{[v-r+1]})^{\top} \right) \\ &= \mathcal{A}^{[v]} C_j \mathbf{R} (\hat{\mathbf{H}}_{\text{inv}}^{[v]})^{\top}, \end{aligned} $$

and where

$$ \hat{\mathbf{H}}_{\text{inv}} \stackrel{\text{def}}{=} \begin{pmatrix} \mathcal{A} \\ \vdots \\ \mathcal{A}^{-[r-1]} \end{pmatrix} \in \mathcal{M}_{m,r}(\mathbb{F}_{q^m}). $$

Using Lemma 3, we then compute the Jacobian matrix of these equations with respect to the $C_j$ variables with $\mathbf{A} \stackrel{\text{def}}{=} \mathcal{A}^{[v]}$, $\mathbf{X} \stackrel{\text{def}}{=} C_j$ and $\mathbf{Y} \stackrel{\text{def}}{=} R (\hat{\mathbf{H}}_{\text{inv}}^{[v]})^{\top}$. This gives

$$ \text{Jac}_{\text{row}(C_j)}(g_{1,\ell_1,j} \dots g_{r,\ell_r,j}) = \mathcal{A}^{[v]} \otimes \hat{\mathbf{H}}_{\text{inv}}^{[v]} \mathbf{R}^{\top}. $$
We can continue as above to obtain Lemma 5, whose proof is analogous to the one of Lemma 4.

**Lemma 5** For any fixed column $\mathbf{h}_j$ in $\mathbf{H}_{pub}$, for $0 \le \ell \le m-1$ and for a modulus $0 \le v \le m-1$, there are $\binom{r}{\lambda+1}$ degree falls from degree $\lambda+2$ to $\lambda+1$ which are given by the maximal minors of the matrix

$$ \mathcal{N}_{j,\ell,v} \stackrel{\text{def}}{=} \begin{pmatrix} \widehat{\mathbf{h}}_j^{[\ell]} (\mathbf{V}^{[\ell]})^{\text{T}} \\ \mathbf{R} (\hat{\mathbf{H}}_{inv}^{[v]})^{\text{T}} \end{pmatrix}, \qquad (16) $$

where

$$ \hat{\mathbf{H}}_{inv} \stackrel{\text{def}}{=} \begin{pmatrix} \mathcal{A} \\ \vdots \\ \mathcal{A}^{-[r-1]} \end{pmatrix}. $$

By gathering the equations for all columns $\mathbf{h}_j$ in $\mathbf{H}_{pub}$, all indexes $\ell$ and all moduli $v$, we obtain a system of $nm^2(\binom{r}{\lambda+1})$ polynomials of degree $\lambda+1$. Similarly to the above, these polynomials have a bilinear structure: they are bilinear in the entries of the $\mathbf{V}^{[\ell]}$'s and in the maximal minors $r_T$ of $\mathbf{R}$. Coming back to the **System 1** over $\mathbb{F}_q$ that we want to solve, this will correspond to an extra set of $nm^2(\binom{r}{\lambda+1})$ polynomials of degree $\lambda+1$ which are produced in degree $\lambda+2$ by the computation. They can also be seen as an affine bilinear system involving $mr^2(\binom{m}{\lambda})$ quadratic monomials.

## 8.3 Approach based on degree fall polynomials

Instead of simply solving the original bilinear system, our results suggest another method by focusing on a system of degree fall polynomials of degree $\lambda+1$. It would consist of the one given by Lemma 4, Lemma 5 or a subset of such equations. As we have just seen, this approach would benefit from the compactness of these polynomials since they have a specific bilinear structure. Its analysis is left for future work, including the study of linear dependencies and the possibility of using hybrid techniques.

In the case of the Rank Decoding Problem, solving the system given by the MaxMinors equations [6] lead to a significant improvement compared to attacks based on Ourivski-Johansson [21,4]. In our case, however, the same will not necessarily hold. First, the ratio between equations and variables in Lemma 4 or Lemma 5 seems less favorable than in [6]. Second, our experiments suggest that the degree falls polynomials in degree $\lambda+2$ do not mark the end of the computation on the original system in general, whereas it was often the case for the Rank Decoding Problem [18,4].

# 9 Conclusion

In the paper we presented two different approaches to distinguish a public-key from random.
The combinatorial approach seems to have reached its limits as is the case for
the problem of decoding in rank metric and we do not expect significant gain (say
non-polynomial improvements on the complexity) from further improvements,
except if there is a major theoretical breakthrough, but who would probably also
extend to the problem of decoding in rank metric.

Concerning the algebraic approach, it is more difficult to ascertain that no
significant improvements are to be expected. Namely, as is the case for solving
non-linear system, a smarter approach to rewrite the system could lead to major
improvements. Anyway it is certainly an interesting field of research to obtain a
finer analysis of system solving.

References

1. Aragon, N., Dyseryn, V., Gaborit, P., Loidreau, P., Renner, J., Wachter-Zeh, A.: LowMS: a new rank metric code-based KEM without ideal structure. Cryptology ePrint Archive, Paper 2022/1596 (2022), https://eprint.iacr.org/2022/1596, https://eprint.iacr.org/2022/1596

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

3. Bardet, M., Briaud, P.: An algebraic approach to the Rank Support Learning problem. In: Cheon, J.H., Tillich, J.P. (eds.) PQCrypto. lncs, Springer International Publishing (2021)

4. Bardet, M., Briaud, P., Bros, M., Gaborit, P., Neiger, V., Ruatta, O., Tillich, J.: An Algebraic Attack on Rank Metric Code-Based Cryptosystems. In: Advances in Cryptology - EUROCRYPT 2020 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020. Proceedings (2020), https://doi.org/10.1007/978-3-030-45727-3_3

5. Bardet, M., Briaud, P., Bros, M., Gaborit, P., Tillich, J.P.: Revisiting Algebraic Attacks on MinRank and on the Rank Decoding Problem. Cryptology ePrint Archive, Paper 2022/1031 (2022), https://eprint.iacr.org/2022/1031, https://eprint.iacr.org/2022/1031

6. 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: 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

7. Chabaud, F., Stern, J.: The Cryptographic Security of the Syndrome Decod-
ing Problem for Rank Distance Codes. In: Advances in Cryptology - ASI-
ACRYPT 1996. LNCS, vol. 1163, pp. 368–381. Springer, Kyongju, Korea (Nov
1996)

8. Coggia, D., Couvreur, A.: On the security of a Loidreau rank metric code based encryption scheme. Des. Codes Cryptogr. 88(9), 1941–1957 (2020)

9. Coppersmith, D.: Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm. Mathematics of Computation 62, 333–350 (1994)

10. Delsarte, P.: Bilinear Forms over a Finite Field, with Applications to Coding Theory. J. Comb. Theory, Ser. A 25(3), 226–241 (1978)
11. Faugère, J.C.: A New Efficient Algorithm for Computing Gröbner Bases (F4). J. Pure Appl. Algebra **139**(1-3), 61–88 (1999)

12. Faugère, J.C.: A New Efficient Algorithm for Computing Gröbner Bases without Reduction to Zero: F5. In: Proceedings ISSAC'02. pp. 75–83. ACM press (2002)

13. Faugère, J.C., Safey El Din, M., Spacodecrenlehauer, P.J.: Gröbner bases of bi-homogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity. J. Symbolic Comput. **46**(4), 406–437 (2011)

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

15. 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)

16. Gaborit, P., Hauteville, A., Phan, D.H., Tillich, J.: Identity-based Encryption from Rank Metric. In: Advances in Cryptology - CRYPTO2017. LNCS, vol. 10403, pp. 194–226. Springer, Santa Barbara, CA, USA (Aug 2017), https://doi.org/10.1007/978-3-319-63697-9_7

17. Gaborit, P., Ruatta, O., Schrek, J.: On the Complexity of the Rank Syndrome Decoding Problem. IEEE Trans. Information Theory **62**(2), 1006–1019 (2016)

18. 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.oew.ac.at/specsem/srs/groeb/download/Levy.pdf

19. Loidreau, P.: A new rank metric codes based encryption scheme. In: Post-Quantum Cryptography 2017. LNCS, vol. 10346, pp. 3–17. Springer (2017)

20. McEliece, R.J.: A Public-Key System Based on Algebraic Coding Theory, pp. 114–116. Jet Propulsion Lab (1978), dSN Progress Report 44

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

22. Overbeck, R.: A New Structural Attack for GPT and Variants. In: Mycrypt. LNCS, vol. 3715, pp. 50–63 (2005)

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