# A polynomial time key-recovery attack on the Sidon cryptosystem

Pierre Briaud, Jean-Pierre Tillich, Javier Verbel

► To cite this version:

Pierre Briaud, Jean-Pierre Tillich, Javier Verbel. A polynomial time key-recovery attack on the Sidon cryptosystem. SAC 2021 - Selected Areas in Cryptography, Sep 2021, Victoria, Canada. pp.419-438, 10.1007/978-3-030-99277-4_20. hal-03533464

HAL Id: hal-03533464

https://hal.science/hal-03533464

Submitted on 18 Jan 2022

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
# A polynomial time key-recovery attack on the Sidon cryptosystem.

Pierre Briaud¹,², Jean-Pierre Tillich¹, and Javier Verbel³

¹ Sorbonne Universités, UPMC Univ Paris 06, Paris, France

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

jean-pierre.tillich@inria.fr

³ Cryptography Research Centre, Technology Innovation Institute, Abu Dhabi, UAE
javier.verbel@tii.ae

**Abstract.** The Sidon cryptosystem [22] is a new multivariate encryption scheme based on the theory of Sidon spaces which was presented at PKC 2021. As is usual for this kind of schemes, its security relies on the hardness of solving particular instances of the MQ problem and of the MinRank problem. A nice feature of the scheme is that it enjoys a homomorphic property due to the bilinearity of its public polynomials. Unfortunately, we will show that the Sidon cryptosystem can be broken by a polynomial time key-recovery attack. This attack relies on the existence of solutions to the underlying MinRank instance which lie in a subfield and which are inherent to the structure of the secret Sidon space. We prove that such solutions can be found in polynomial time. Our attack consists in recovering an equivalent key for the cryptosystem by exploiting these particular solutions, and this task can be performed very efficiently.

**Keywords:** Multivariate cryptography · Encryption scheme · Algebraic attack · MinRank Problem.

## 1 Introduction.

In recent years, many Public Key Cryptographic (PKC) primitives have been proposed to fulfill the need of having quantum-secure Key Encapsulation Mechanisms (KEMs) and Digital Signatures Schemes (DSS).

In the field of DSS, Multivariate Public Key Cryptography (MPKC) has proven to be one of the most promising alternatives. In the ongoing NIST-PQC standardization process, the MPKC schemes Rainbow [12] and GeMSS [9] are in the final round, even though the last as an alternative candidate. But when it comes to KEMs, the situation is less promising. Throughout the last 25 years, many MPKC encryption schemes have been proposed such as HFE, ZHFE, Extension Field Cancellation (EFC), SRP, HFERP, EFLASH and the Simple Matrix Encryption Scheme, see [20,26,25,21,17,8], and all of them are either extremely inefficient or have been successfully cryptanalyzed [4,7,1,24,19,18]. A
relative common structure among the MPKC schemes is that the public key is a system of multivariate polynomials which is hard to solve directly. On the contrary, the private key is a sequence of polynomials which is easy to solve and which is masked in certain way to produce the public key. The two main hard problems considered to build MPKC are the problem of solving a system of multivariate quadratic equations over a finite field (the MQ problem) and the following MinRank problem, which was originally defined and proven NP-complete in [6]. The version of the MinRank problem which is relevant in our case is given by

**Problem 1 (MinRank problem).**

*Input:* an integer $r \in \mathbb{N}$, $n$ matrices $\mathbf{M}^{(1)}, \dots, \mathbf{M}^{(n)} \in \mathbb{F}_q^{k \times k}$, $\mathbb{L}$ a finite extension of $\mathbb{F}_q$.

*Output:* field elements $x_1, x_2, \dots, x_n \in \mathbb{L}$, not all zero, such that

$$ \mathrm{Rank} \left( \sum_{i=1}^{n} x_i \mathbf{M}^{(i)} \right) \leq r. $$

Note that the standard formulation in the literature considers $\mathbb{L} = \mathbb{F}_q$ and possibly non-square matrices. In all cases, solving a particular instance of one of these two problems leads to either a key-recovery attack or a message-recovery attack on a given scheme. Thus, the security of the scheme is usually estimated via the hardness of solving particular instances of MQ or MinRank.

At PKC 2021, Raviv, Langton and Tamo proposed, for the first time, a MPKC encryption scheme based on the theory of Sidon spaces [22]. The concept of Sidon space was originally defined in [2]. A Sidon space is an $\mathbb{F}_q$-subspace of an extension field $\mathbb{F}_{q^n}$ in which the product of any two elements factors uniquely up to multiplicative constants in $\mathbb{F}_q$. The basic idea of the scheme is as follows: the plaintext is the equivalence class of pairs of two elements in a Sidon space $\mathcal{V}$ of dimension $k$, two pairs with the same product being equivalent, while the ciphertext is the product of these two elements. The private key is some information related to the structure of $\mathcal{V}$ that allows to factor efficiently any ciphertext, while the public key is a bilinear sequence $(p_1, \dots, p_{2k})$ of $2k$ homogeneous equations in two blocks of variables $\mathbf{a}$ and $\mathbf{b}$ over $\mathbb{F}_q$ of equal size $k$. This makes the Sidon cryptosystem to have an additive homomorphic property since the sum of the encryptions of two messages like $\{\mathbf{a}_1, \mathbf{b}\}, \{\mathbf{a}_2, \mathbf{b}\}$ results in the encryption of $\{\mathbf{a}_1 + \mathbf{a}_2, \mathbf{b}\}$. To the best of our knowledge, this is first MQ- or MinRank- based scheme doted with any kind of homomorphic property.

The private key can be obtained from a solution to the MinRank problem given by the matrices $\mathbf{M}^{(i)} \in \mathbb{F}_q^{k \times k}$ defined by $p_i(\mathbf{a}, \mathbf{b}) = \mathbf{a} \mathbf{M}^{(i)} \mathbf{b}^\top$ for $1 \le i \le n = 2k$, with $r = 1$ and $\mathbb{L} = \mathbb{F}_{q^{2k}}$. It turns out that this MinRank instance has many solutions, and the structure of the Sidon space can be fully extracted from at least one of these solutions. However, to perform a key-recovery attack, the authors argue that

(i) it is not clear how to solve this particular MinRank instance, since standard techniques are strongly based either on the fact that the base field is small (Linear
Algebra Search [16]) or the number of solutions is small (Minors modeling [13] + XL, and Support-Minors modeling [3]).

(ii) Even if one is able to find a solution to the MinRank problem, it is not clear how this solution can be used to develop a key recovery.

Therefore, the message-recovery attack is arguably the most threatening attack which may be used to design parameters, and this attack can be performed by inverting the public bilinear system. When $q$ is large enough, the Gröbner basis approach outperforms the exhaustive search on $\mathbf{a}$ or $\mathbf{b}$ in $O(k^3q^{k-1})$, and the authors claim a complexity of

$$ \mathcal{O}\left(\binom{3k+1}{k+1}^{\omega}\right) \qquad (1) $$

operations in $\mathbb{F}_q$ for this attack, where $2 \le \omega \le 3$ is the linear algebra constant. This cost is clearly exponential in $k$.

**Contributions.** The purpose of this paper is to give a polynomial-time attack breaking the Sidon cryptosystem. Our attack relies on a rigorous analysis of the solution set of the underlying MinRank problem. In particular, we show here that in addition to generic solutions over $\mathbb{F}_{q^{2k}}$, there exist solutions over the subfield $\mathbb{F}_{q^k}$. Moreover, all these solutions over $\mathbb{F}_{q^k}$ are inherent to the Sidon space used in the scheme. Our attack can be summarized as follows

- The first step of our attack consists in recovering these solutions over $\mathbb{F}_{q^k}$. To this end, we propose a dedicated modeling of the MinRank problem and prove that for this modeling the Gröbner basis computation on this algebraic system terminates at degree 3 independently from the value of $k$. This shows that this first step can be achieved in polynomial time.

- Second, it is possible to exploit these solutions in order to find an equivalent key which is another Sidon space. This second step can be performed by simple linear algebra operations followed by a sub-algorithm of the original key generation process. Therefore, its cost is also expected to be polynomial.

Along with this paper, we provide a sage implementation of our attack in [5]. This tool can also be used to verify experimentally all the theoretical claims made in the paper and to reproduce the experiments we performed.

**Roadmap.** The Sidon cryptosystem from [22] is presented in Section 2. In Section 3, we provide a detailed analysis of the underlying MinRank instance, and this material allows us to introduce our key-recovery attack in Section 4 and in Section 5.

**Notation.** Row vectors are denoted by bold lowercase letters ($\mathbf{u}, \mathbf{v}, \dots$) and matrices are denoted by bold uppercase letters ($\mathbf{M}, \mathbf{N}, \dots$). For a vector $\mathbf{v}$ we use the notation $v_i$ for the $i$-th component of $\mathbf{v}$, and for a matrix $\mathbf{M}$ we use the notation $\mathbf{M}_{i,j}$ for the entry in row $i$ and column $j$.
For $\mathbf{v}$ a vector of length $k$, we denote by $\mathcal{M}(\mathbf{v})$ the rank 1 symmetric matrix of size $k \times k$ which is equal to $\mathbf{v}^\mathrm{T}\mathbf{v}$. In the following, $q \ge 3$ is a prime power, and we will consider finite extensions of $\mathbb{F}_q$, namely $\mathbb{F}_{q^k}$ and $\mathbb{F}_{q^{2k}}$. For $j \in \mathbb{Z}_{\ge 0}$ and $\mathbf{v} = (v_1, \dots, v_k)$ a vector whose entries are elements or polynomials over a finite extension of $\mathbb{F}_q$, we define

$$ \mathbf{v}^{[j]} := (v_1^{q^j}, \dots, v_k^{q^j}). $$

This corresponds to applying the Frobenius automorphism $x \mapsto x^q$ $j$ times on each coordinate of $\mathbf{v}$. Note that this field automorphism is the identity on $\mathbb{F}_q$. We will adopt the same notation for matrices, namely the matrix $\mathcal{M}^{[j]}$ is the matrix obtained from $\mathcal{M}$ by raising all its entries to the power $q^j$.

We will also adopt in several places a coding theoretic point of view and view a subspace $\mathcal{C}$ of $\mathbb{F}_q^N$ as a linear code and use the term *parity-check* for it to denote a matrix $\mathbf{H}$ whose null-space is $\mathcal{C}$, that is:

$$ \mathcal{C} = \{ \mathbf{x} \in \mathbb{F}_q^N : \mathbf{H}\mathbf{x}^{\mathrm{T}} = \mathbf{0} \}. $$

Finally, it is convenient to consider for a vector space $V$, ordered bases for it, and we will use a vector notation for the basis.

**Polynomial systems.** In the following, the expression $\mathbb{K}[\mathbf{x}]$ denotes the polynomial ring over the field $\mathbb{K}$ in the coordinates of $\mathbf{x} = (x_1, \dots, x_k)$. We will use Gröbner basis techniques to solve polynomial systems, and we refer the reader to [10] for basic definitions and properties of monomial orderings and Gröbner bases.

# 2 The Sidon cryptosystem.

Several explicit constructions of Sidon spaces with relevant parameters and factoring properties were proposed in [23], and the one used in [22] to instantiate the Sidon cryptosystem is of this kind. In Section 2.1, we give some background on Sidon spaces in general and on this specific construction. The Sidon cryptosystem is presented in Section 2.2, and in Section 2.3 we discuss the important notion of equivalent keys for this scheme.

## 2.1 Sidon spaces.

For integers $k$ and $n$ and $q$ a prime power, let $\mathcal{G}_q(n, k)$ be the set of all $\mathbb{F}_q$-subspaces of $\mathbb{F}_q^n$ of dimension $k$. The formal definition of a Sidon space is the following.

**Definition 1.** A subspace $V \in \mathcal{G}_q(n, k)$ is called a Sidon space if for all non-zero $a, b, c, d \in V$, if $ab = cd$, then $\{a\mathbb{F}_q, b\mathbb{F}_q\} = \{c\mathbb{F}_q, d\mathbb{F}_q\}$.
Then, a first natural question is whether if there exist Sidon spaces of arbitrary dimension. A constraint on $k$ was given by [2, Thm. 18][23, Prop. 3], where it is proven that if $\mathcal{V} \in \mathcal{G}_q(n, k)$ is a Sidon space, then one has

$$ \dim_{\mathbb{F}_q}(\mathcal{V}^2) \geq 2k $$

with $\mathcal{V}^2 = \operatorname{span}_{\mathbb{F}_q}\{uv \mid u, v \in \mathcal{V}\}$. Since $\mathcal{V}^2 \subset \mathbb{F}_{q^n}$, this implies that $k \leq n/2$, and Sidon spaces for which this bound is an equality are referred as *min-span*. Note that regardless of the existence of any factoring algorithm for $\mathcal{V}$, it is crucial for the security of the cryptosystem that the dimension of $\mathcal{V}$ satisfies $k = \Theta(n)$, as pointed out in [22, Rem. 2]. In particular, the construction considered to devise the scheme is a *min-span* Sidon space, i.e. $n = 2k$. To describe this construction, let $W_{q-1} = \{u^{q-1} \mid u \in \mathbb{F}_{q^k}\}$ and $\overline{W}_{q-1} = \mathbb{F}_{q^k} \setminus W_{q-1}$.

**Construction 1** [23, Const. 15] For $q \geq 3$ a prime power and $k$ a positive integer, let $n = 2k$ and let $\gamma \in \mathbb{F}_{q^n}^*$ be a root of an irreducible polynomial $x^2+bx+c$ over $\mathbb{F}_{q^k}$ such that $c \in \overline{W}_{q-1}^4$. Then, the subspace $\mathcal{V} = \{u+u^q\gamma \mid u \in \mathbb{F}_{q^k}\} \subset \mathbb{F}_{q^n}$ is a Sidon space of dimension $k$.

A Sidon space $\mathcal{V}$ given by Construction 1 admits the following efficient factoring algorithm. This algorithm fully uses the knowledge of the element $\gamma$ such that $\mathcal{B} := \{1, \gamma\}$ is a basis of $\mathbb{F}_{q^{2k}}$ over $\mathbb{F}_{q^k}$, and for $x \in \mathbb{F}_{q^{2k}}$ we will denote by $[1](x)$ and $[\gamma](x)$ the components of $x$ in this basis. Given a product $\pi = \pi_1\pi_2$ where $\pi_1$ and $\pi_2$ lie in $\mathcal{V}$, Algorithm 1 recovers $\pi_1$ and $\pi_2$ up to constant factors in $\mathbb{F}_q$.

**Input:** A product $\pi = \pi_1\pi_2$, where $\pi_1 = u + u^q\gamma$ and $\pi_2 = v + v^q\gamma \in \mathcal{V}$, the element $\gamma \in \mathbb{F}_{q^n}^*$ such that $\gamma^2 + b\gamma + c = 0$ from Construction 1.

**Output:** $\{\pi_1\mathbb{F}_q, \pi_2\mathbb{F}_q\}$.

Decompose $\pi$ in the basis $\{1, \gamma\}$:

$$ q_0 \leftarrow [1](\pi) \qquad \text{// } q_0 = uv - c(uv)^q $$

$$ q_1 \leftarrow [\gamma](\pi) \qquad \text{// } q_1 = uv^q + u^q v - b(uv)^q $$

$$ A \leftarrow T^{-1}(q_0) \qquad \text{// where } T \text{ is map } x \mapsto x - cx^q, A = uv $$

$$ B \leftarrow q_1 + bA^q \qquad \text{// } B = uv^q + u^q v $$

Compute the roots $\alpha, \beta$ of $A + Bx + A^q x^2$

$$ \text{// } \alpha = -1/u^{q-1}, \beta = -1/v^{q-1} $$

From $\alpha$ and $\beta$, recover $\{u\mathbb{F}_q, v\mathbb{F}_q\}$ uniquely and therefore $\{\pi_1\mathbb{F}_q, \pi_2\mathbb{F}_q\}$.

**Algorithm 1:** Factoring algorithm for Sidon space from Construction 1.

## 2.2 Description of the cryptosystem.

The Sidon cryptosystem relies on Construction 1, but it might be possible to consider another type of Sidon space such that $k = \Theta(n)$ for which an efficient factoring algorithm exists. In this section, we briefly describe the building blocks of the scheme, and we refer the reader to [22, §3] for further details.

<footnote n="4">⁴ Such a polynomial is known to exist by [23, Corollary 14].</footnote>
## Keygen:

- Select a random element $\gamma \in \mathbb{F}_{q^n}$ satisfying the constraints given in Construction 1 in order to build the Sidon space $\mathcal{V} := \{u + u^q\gamma|u \in \mathbb{F}_{q^k}\}$.

- Select $\nu = (\nu_1, \dots, \nu_k)$ a random basis of $\mathcal{V}$ and $\beta = (\beta_1, \dots, \beta_n)$ a random basis of $\mathbb{F}_{q^n}$ over $\mathbb{F}_q$.

- Represent the matrix $M(\nu) = \nu^T \nu \in \mathbb{F}_{q^n}^{k \times k}$ over the basis $\beta$:

$$M(\nu) = \nu^T \nu = \sum_{i=1}^{n} \beta_i M^{(i)},$$

where $M^{(i)} \in \mathbb{F}_q^{k \times k}$ for $1 \le i \le n$.

- Output $sk = (\beta, \nu, \gamma)$ as secret key and $pk = (M^{(1)}, \dots, M^{(n)})$ as public key.

As explained in the introduction, the message space correspond to the equivalence class of pairs of elements $\{a, b\}$ in the Sidon space $\mathcal{V}$, two pairs $\{a, b\}$ and $\{c, d\}$ being equivalent if their product is the same: $ab = cd$. If one views an element $a$ of $\mathcal{V}$ as a vector $a \in \mathbb{F}_q^k$, i.e. $a = \sum_{i=1}^k a_i \nu_i$, then the equivalence class associated to $\{a, b\}$ corresponds to all pairs $\{c, d\}$ such that either $a^T b = c^T d$ or $a^T b = d^T c$. This space is of size $\frac{(q^k - 1)(q^k - q)}{2(q - 1)} + q^k - 1$ as shown in [22, App A].

### Encrypt($\{a, b\}, pk = (M^{(i)})_{i=1}^n$):

- The ciphertext associated to (the equivalence class of) $\{a, b\}$ is

$$c = (c_i)_{i=1}^n = (aM^{(i)}b^T)_{i=1}^n \in \mathbb{F}_q^n. \quad (2)$$

Note that this definition is compatible with the way the plaintext is defined: the ciphertext does not depend on the particular pair $\{a, b\}$ chosen in the equivalence class of the message. An interesting property of the Sidon cryptosystem is that it is homomorphic under the addition on half of the plaintext. That is, for two given plaintexts $\{a_1, b\}$ and $\{a_2, b\}$ we have

$$\text{Encrypt}(\{a_1, b\}, pk) + \text{Encrypt}(\{a_2, b\}, pk) = \text{Encrypt}(\{a_1 + a_2, b\}, pk).$$

To decrypt with the secret key, Bob views the ciphertext $c$ as a product of elements in $\mathcal{V}$. Then, he is able to recover the factors using Algorithm 1 since he completely knows the structure of $\mathcal{V}$.
Decrypt(c, sk = (β, ν, γ)):

– Compute

$$
\begin{align}
\sum_{i=1}^{n} \beta_i c_i &= \sum_{i=1}^{n} \beta_i (a M^{(i)} b^{\top}) = a M(\nu) b^{\top} \nonumber \\
&= a \nu^{\top} \nu b^{\top} = \left(\sum_{i=1}^{k} a_i \nu_i\right) \left(\sum_{i=1}^{k} b_i \nu_i\right) = ab, \tag{3}
\end{align}
$$

and ab is a product of elements in V.

- From the knowledge of $\gamma$, use Algorithm 1 to recover $\{a, b\}$ up to a multiplicative factor in $\mathbb{F}_q$.

- Finally, retrieve $\{a, b\}$ (up to a multiplicative factor) by representing $\{a, b\}$ over the basis $\nu$. Such an $\{a, b\}$ defines the message in a unique way.

2.3 Equivalent keys for the Sidon cryptosystem.

An important notion for multivariate schemes in general is that of equivalent keys. Two secret keys are equivalent if they lead to the same public key. In the case of the Sidon cryptosystem, one can easily obtain the following result by using the definition of the decryption process given in Equation (3):

**Fact 1** Any Sidon space $V'$ generated using Construction 1 with basis $\nu'$ and such that the matrix $M(\nu')$ lies in the linear span of the $M^{(i)}$'s can be used as an equivalent key.

Equivalent keys are an important feature for our attack, since it will consist
in recovering a Sidon space $V' \neq V$ which allows to decrypt any ciphertext.

3 Analysis of the underlying MinRank problem.

Given the public key ($M^{(1)}, \dots, M^{(n)}$) such that $M^{(i)} \in \mathbb{F}_q^{k \times k}$ for $1 \le i \le n$, one has

$$
M(\nu) = \nu^{\top}\nu = \sum_{i=1}^{n} \beta_i M^{(i)},
$$

where $(\beta_1, \dots, \beta_n)$ is the basis of $\mathbb{F}_{q^n}$ over $\mathbb{F}_q$ and $\nu$ is the basis of the Sidon
space which are part of the private key. In other words, the matrix $M(\nu)$ is a
linear combination of the $M^{(i)}$'s over $\mathbb{F}_{q^n}$ which has rank 1, and a key-recovery
attack on the scheme requires to find specific solutions over $\mathbb{F}_{q^n}$ of the MinRank
instance described by the $M^{(i)}$'s. This MinRank problem is not standard in at
least two ways. First, solutions are searched in the extension field $\mathbb{F}_{q^n}$, whereas
the $M^{(i)}$'s have their entries in $\mathbb{F}_q$. Second, this system has surprisingly many
solutions and it is not clear at all whether the Sidon structure can be recovered
from an arbitrary solution to it. Note that the authors of [22] only studied
the hardness of finding any solution to this MinRank problem, and the task of determining the whole solution set was not addressed explicitly.

In this section, we examine in greater depth the properties of this solution set. A first remark is that the solutions correspond to rank 1 matrices in the space generated by the $M^{(i)}$'s over $\mathbb{F}_{q^n}$:

$$ C_{mat} := \langle M^{(1)}, \dots, M^{(n)} \rangle_{\mathbb{F}_{q^n}}. \qquad (4) $$

Our main result will be the existence of solutions over the subfield $\mathbb{F}_{q^k}$, i.e. rank 1 matrices in

$$ D_{mat} := C_{mat}|_{\mathbb{F}_{q^k}} := C_{mat} \cap \mathbb{F}_{q^k}^{k \times k}. $$

**Fact 2** The subspace $D_{mat} = C_{mat}|_{\mathbb{F}_{q^k}}$ contains elements of rank 1.

Such elements are described in Section 3.3, and our experiments suggest that these are the only ones in $D_{mat}$. A reader only interested in our key-recovery attack can directly go to Section 4 and Section 5.

## 3.1 Restricting the number of the solutions.

We start by reviewing some elementary properties of the solution set. Since the generators $M^{(i)}$ are symmetric, all the elements in $C_{mat}$ are symmetric as well. Therefore, rank 1 elements in $C_{mat}$ will be of the form $x^T y \in \mathbb{F}_{q^n}^{k \times k}$ for $x$ collinear with $y$. In particular, we will be interested in the following subset of solutions defined by

$$ Z_{\mathbb{F}_{q^n}} := \{x \in \mathbb{F}_{q^n}^k, x^T x \in C_{mat}\}. \qquad (5) $$

This set is non-trivial since it contains $\nu$ from the private key. Also, there is still one degree of freedom coming from the $\mathbb{F}_{q^n}$-linearity of $C_{mat}$. For instance, since $\nu_1 \neq 0$ in $\nu$, the set

$$ Z_{\mathbb{F}_{q^n}, s} := \{x \in Z_{\mathbb{F}_{q^n}}, x_1 = s\} $$

is also non-trivial for $s \in \mathbb{F}_{q^n}^*$.

## 3.2 Generic solutions over $\mathbb{F}_{q^n}$.

In this section, we describe a generic way to generate many solutions to the MinRank problem. Consider any $\omega \in \mathbb{F}_{q^n}^k$ such that $\omega \in Z_{\mathbb{F}_{q^n}}$. By definition, there exists $\eta = (\eta_1, \dots, \eta_n) \in \mathbb{F}_{q^n}^n$ such that

$$ M(\omega) = \sum_{\ell=1}^{n} \eta_{\ell} M^{(\ell)}. \qquad (6) $$

In particular, one has for $1 \le i, j \le k$:

$$ \omega_i \omega_j = \sum_{\ell=1}^{n} \eta_{\ell} M_{i,j}^{(\ell)}. \qquad (7) $$
Then, by iterating the Frobenius map $p$ times on this equation for $0 \le p \le n-1$, one obtains

$$ \omega_i^{[p]} \omega_j^{[p]} = \sum_{\ell=1}^{n} \eta_{\ell}^{[p]} \mathbf{M}_{i,j}^{(\ell)} \quad (8) $$

since the matrices $\mathbf{M}^{(\ell)}$ have entries in $\mathbb{F}_q$. This implies that the matrix

$$ \mathbf{M}(\omega^{[p]}) = \sum_{\ell=1}^{n} \eta_{\ell}^{[p]} \mathbf{M}^{(\ell)} \quad (9) $$

belongs to $C_{\text{mat}}$ for $0 \le p \le n-1$. Overall, this observation can be summarized in the following Lemma 1.

**Lemma 1 ("Stability by Frobenius")** Let $C_{\text{mat}}$ as defined in Equation (4) and let $\mathcal{Z}_{\mathbb{F}_{q^n}}$ as defined in Equation (4). If $\omega \in \mathcal{Z}_{\mathbb{F}_{q^n}}$, then $\omega^{[j]} \in \mathcal{Z}_{\mathbb{F}_{q^n}}$ for any $j \ge 0$, and more generally if $\mathbf{M} \in C_{\text{mat}}$, then $\mathbf{M}^{[j]} \in C_{\text{mat}}$ for any $j \ge 0$.

The fact that $\mathcal{V}$ is a Sidon space is not used at all in this reasoning. In particular, the very same argument can be applied to a random subspace $\mathcal{W} \subset \mathbb{F}_{q^n}$ of dimension $k$ along with a random secret basis $\omega$ for $\mathcal{W}$. In this case, the $\mathbf{M}^{(i)}$'s are obtained from the decomposition of the matrix $\mathbf{M}(\omega)$ in an arbitrary basis of $\mathbb{F}_{q^n}$ over $\mathbb{F}_q$, and $C_{\text{mat}}$ and $\mathcal{Z}_{\mathbb{F}_{q^n}}$ are defined in the same way as before. For such a random subspace $\mathcal{W}$, the only solutions to the MinRank instance that we observe in practice are given by Lemma 1:

**Observation 1 (From experiments)** Let $\mathcal{W} \subset \mathbb{F}_{q^n}$ be a random $\mathbb{F}_q$-subspace of dimension $k$, let $\omega$ be a random basis of $\mathcal{W}$ and let $s \in \mathbb{F}_{q^n}^*$. One has

$$ |\mathcal{Z}_{\mathbb{F}_{q^n}, s}| = n. $$

Moreover, if $s \in \mathbb{F}_q^*$, then there exists $\mathbf{u} \in \mathbb{F}_{q^n}^k$ with $u_1 = s$ such that

$$ \mathcal{Z}_{\mathbb{F}_{q^n}, s} = \{\mathbf{u}, \mathbf{u}^{[1]}, \dots, \mathbf{u}^{[n-1]}\}. $$

However, when $\mathcal{V}$ is a Sidon space generated using Construction 1, we observed that there were many more solutions to the MinRank instance than those just described. This behavior can be explained by the fact that there also exist rank 1 linear combinations of the $\mathbf{M}^{(i)}$'s over the subfield $\mathbb{F}_{q^k}$, i.e. the set $\mathcal{Z}_{\mathbb{F}_{q^k}}$ is non-trivial. More precisely, we obtained the following experimental result.

**Observation 2 (From experiments)** Let $\mathcal{V}$ be a Sidon space generated using Construction 1. For $s \in \mathbb{F}_{q^k}^*$, we observed that

$$ |\mathcal{Z}_{\mathbb{F}_{q^k}, s}| = k(q^k - 1). $$

Moreover, if $t \in \mathbb{F}_{q^k}^*$, $t \notin \langle s \rangle_{\mathbb{F}_q}$, we observed that

$$ |\{x \in \mathcal{Z}_{\mathbb{F}_{q^k}, s}, x_2 = t\}| = k. $$
### 3.3 Rank 1 codewords in $D_{mat}$ from the Sidon structure.

This section is dedicated to the study of the set $Z_{F_{q^k}}$ when $V$ is a Sidon space generated using Construction 1 with secret basis $\nu$. For $1 \le i \le k$, there exists $u_i \in F_{q^k}$ such that

$$ \nu_i = u_i + u_i^q \gamma. \qquad (10) $$

Note that $\mathbf{u} := (u_1, \dots, u_k)$ is necessarily a basis of $F_{q^k}$ over $F_q$. In the following Proposition 1, we are interested in the rank 1 matrix

$$ \mathbf{M}(\mathbf{u}) = (u_1, \dots, u_k)^{\mathrm{T}}(u_1, \dots, u_k) \in \mathbb{F}_{q^k}^{k \times k}. $$

**Proposition 1** Let $\mathbf{M}^{(1)}, \dots, \mathbf{M}^{(n)}$ be the public matrices associated to the secret Sidon space $V$ and let $\mathbf{u}$ be the basis of $F_{q^k}$ over $F_q$ associated to $\nu$ by Equation (10). Then, $\mathbf{M}(\mathbf{u})$ is a rank 1 matrix in $D_{mat}$. Moreover, the same is true for $\mathbf{M}(\mathbf{u}^{[j]})$ for $0 \le j \le k-1$.

*Proof.* We do the proof for $\mathbf{M}(\mathbf{u}) = \mathbf{M}(\mathbf{u}^{[0]})$ and the rest easily follows by using Lemma 1. First, one can write $\mathbf{M}(\nu)$ as a sum

$$ \mathbf{M}(\nu) = \mathbf{A} + \gamma \mathbf{B} \qquad (11) $$

where the matrices $\mathbf{A}, \mathbf{B} \in \mathbb{F}_{q^k}^{k \times k}$ are such that

$$ \left\{ \begin{array}{l} \mathbf{A} = \sum_{i=1}^{n} \delta_i \mathbf{M}^{(i)} \\ \\ \mathbf{B} = \sum_{i=1}^{n} \eta_i \mathbf{M}^{(i)} \end{array} \right. \qquad (12) $$

and where $\beta_i := \delta_i + \gamma\eta_i$ is expressed in the basis $\{1, \gamma\}$ for $1 \le i \le n$ with $\delta_i, \eta_i \in F_{q^k}$. Also, recall that the primitive element $\gamma$ is a root of the irreducible polynomial $x^2 + bx + c$ over $F_{q^k}$, so that one obtains for $1 \le i, j \le k$:

$$ \begin{aligned} \nu_i \nu_j &= (u_i + u_i^q \gamma)(u_j + u_j^q \gamma) \\ &= (u_i u_j - c(u_i u_j)^q) + \gamma(u_i u_j^q + u_i^q u_j - b(u_i u_j)^q). \end{aligned} \qquad (13) $$

Therefore, Equation (13) shows that $\mathbf{A} = \mathbf{M}(\mathbf{u}) - c\mathbf{M}(\mathbf{u}^{[1]})$, and this matrix belongs to $D_{mat}$ by (12). By Lemma 1, the same is true for the following matrices

$$ \begin{aligned} \mathbf{A}^{[1]} &= \mathbf{M}(\mathbf{u}^{[1]}) - c^q \mathbf{M}(\mathbf{u}^{[2]}) \\ \mathbf{A}^{[2]} &= \mathbf{M}(\mathbf{u}^{[2]}) - c^{q^2} \mathbf{M}(\mathbf{u}^{[3]}) \\ \vdots \\ \mathbf{A}^{[k-1]} &= \mathbf{M}(\mathbf{u}^{[k-1]}) - c^{q^{k-1}} \mathbf{M}(\mathbf{u}^{[k]}) = \mathbf{M}(\mathbf{u}^{[k-1]}) - c^{q^{k-1}} \mathbf{M}(\mathbf{u}). \end{aligned} $$
Then, by performing linear combinations over $\mathbb{F}_{q^k}$, one gets

$$A + \sum_{i=1}^{k-1} c^{1+q+\cdots+q^{i-1}} A^{[i]} = (1 - c^{1+q+\cdots+q^{k-1}}) M(u) = (1 - c^{\frac{q^{k-1}}{q-1}}) M(u).$$

Finally, one has $c^{\frac{q^{k-1}}{q-1}} \neq 1$ since $c \in \overline{W}_{q-1}$, and therefore the matrix $M(u)$ can be expressed as a linear combination of the $A^{[i]}$'s over $\mathbb{F}_{q^k}$. This proves $M(u) \in \mathcal{D}_{mat}$. $\square$

Also, note that it is easy to find other rank 1 matrices in $\mathcal{D}_{mat}$. Indeed, by using the second term in the right hand side of Equation (13), one notices that the matrix $B \in \mathbb{F}_q^{k \times k}$ defined in the proof of Proposition 1 by (11) satisfies $B_{i,j} = u_i u_j^q + u_i^q u_j - b(u_i u_j)^q$ for $1 \le i, j \le k$, and this matrix also belongs to $\mathcal{D}_{mat}$ by (12). Notice that this equality implies that

$$ \begin{aligned} B &= u^\top u^{[1]} + (u^{[1]})^\top u - b(u^{[1]})^\top u^{[1]} \\ &= u^\top u^{[1]} + (u^{[1]})^\top u - b M(u^{[1]}). \end{aligned} \quad (14) $$

Now, let $\lambda \in \mathbb{F}_{q^k}$ and consider

$$ \begin{aligned} M(u + \lambda u^{[1]}) &= (u + \lambda u^{[1]})^\top (u + \lambda u^{[1]}) \\ &= u^\top u + \lambda^2 (u^{[1]})^\top u^{[1]} + \lambda \left\{ u^\top u^{[1]} + (u^{[1]})^\top u \right\} \\ &= M(u) + \lambda^2 M(u^{[1]}) + \lambda B + \lambda b M(u^{[1]}) \quad (\text{by (14)}). \end{aligned} $$

This implies that $M(u + \lambda u^{[1]})$ belongs to $\mathcal{D}_{mat}$. Since $M(u + \lambda u^{[1]})$ is of rank 1, we have therefore proved the following generalization of Proposition 1.

**Proposition 2** Let $M^{(1)}, \dots, M^{(n)}$ be the public matrices associated to the secret Sidon space $\mathcal{V}$ and let $u$ be the basis of $\mathbb{F}_{q^k}$ over $\mathbb{F}_q$ associated to $\nu$ by Equation (10). One has

$$ \{ \lambda u^{[j]} + \mu u^{[j+1]} : (\lambda, \mu) \in \mathbb{F}_{q^k}^2, 0 \le j \le k-1 \} \subset \mathcal{Z}_{\mathbb{F}_{q^k}}. $$

Finally, note that Observation 2 suggests that the inclusion given in Proposition 2 is an equality. Combined with the content of Section 3.1, this gives a complete understanding of the set of rank 1 codewords in $\mathcal{D}_{mat}$.

In the next sections, we are going to describe our key-recovery attack which builds upon the following facts:

- As pointed out by [22], it seems infeasible to recover the Sidon space $\mathcal{V}$ directly as a solution to the MinRank problem.
– However, from Fact 1, it is possible to decrypt by using a different Sidon space. Moreover, contrary to the approach described in [22, §5.1] which introduces an algebraic system with too many variables to be solved in practice, we will find such a space efficiently. We will then show how this can be exploited to find sufficiently many elements of $\mathcal{Z}_{\mathbb{F}_{q^k}}$ that will be used to recover an equivalent key.

# 4 Solving the MinRank instance over $\mathbb{F}_{q^k}$.

In this section, we show how to determine elements in the set

$$ \mathcal{Z}_{\mathbb{F}_{q^k}} := \{ \mathbf{x} \in \mathbb{F}_{q^k}^k, \mathbf{x}^\top \mathbf{x} \in \mathcal{C}_{\mathrm{mat}} \} = \{ \mathbf{x} \in \mathbb{F}_{q^k}^k, \mathbf{x}^\top \mathbf{x} \in \mathcal{D}_{\mathrm{mat}} \}, $$

which corresponds to particular solutions to the MinRank instance described in the previous section. They will be exploited in Section 5 in order to derive an equivalent key.

## 4.1 Parity-check modeling.

Rather than using the generic techniques described in [22, §4] to target elements in $\mathcal{Z}_{\mathbb{F}_{q^k}}$, we found experimentally that it was more favorable to consider the following algebraic modeling which is largely inspired by [11, §5.4]. A first remark is that a square matrix of size $k$ over $\mathbb{F}_{q^k}$ can also be viewed as a vector of length $k^2$ over $\mathbb{F}_{q^k}$. To make this correspondence explicit, we will use the linear isomorphism

$$ \mathrm{vec} : \mathbb{F}_{q^k}^{k \times k} \to \mathbb{F}_{q^k}^{k^2} \\ M \mapsto m $$

such that $m_{(i-1)k+j} = M_{i,j}$ for $1 \le i, j \le k$, and we consider the following subspace of $\mathbb{F}_{q^k}^{k^2}$

$$ \mathrm{vec}(\mathcal{D}_{\mathrm{mat}}) := \{\mathrm{vec}(M), M \in \mathcal{D}_{\mathrm{mat}}\}. $$

It is a subspace of dimension $n$ over $\mathbb{F}_{q^k}$. We can consider it as linear code and let $H \in \mathbb{F}_{q^k}^{(k^2-n) \times k^2}$ be an arbitrary parity-check matrix for it, i.e. a matrix such that

$$ \mathrm{vec}(\mathcal{D}_{\mathrm{mat}}) = \{ \mathbf{x} \in \mathbb{F}_{q^k}^{k^2}, H \mathbf{x}^\top = 0 \}. $$

Note that since the $M^{(i)}$'s have entries in $\mathbb{F}_q$, it is possible to choose a parity-check matrix whose entries lie in $\mathbb{F}_q$ as well. Finally, let

$$ X := x^\top x = \begin{pmatrix} x_1^2 & x_1 x_2 & \cdots & x_1 x_k \\ x_2 x_1 & x_2^2 & \cdots & x_2 x_k \\ \vdots & \vdots & \ddots & \vdots \\ x_k x_1 & x_k x_2 & \cdots & x_k^2 \end{pmatrix} \quad (15) $$
be a matrix in the unknowns $x_i$ corresponding to a solution $x \in \mathbb{Z}_{\mathbb{F}_{q^k}}$. Since the vector $\text{vec}(\mathbf{X})$ belongs to $\text{vec}(\mathcal{D}_{\text{mat}})$, one obtains the following system of $k^2 - 2k$ quadratic equations given by

$$ \mathbf{H} \text{vec}(\mathbf{X})^{\top} = 0. \qquad (16) $$

**Lemma 2** The sequence given by Equation (16) contains at most $k^2 - 2k - \binom{k}{2}$ linearly independent quadratic polynomials over $\mathbb{F}_{q^k}$.

*Proof.* Let $(e_1, \dots, e_{k^2})$ be the canonical basis of $\mathbb{F}_{q^k}^{k^2}$. Owing to the symmetry of the $M^{(i)}$'s, one obtains that for $1 \le i < j \le k$, the vector

$$ \sigma_{i,j} = e_{(i-1)k+j} - e_{(j-1)k+i} $$

belongs to the dual code $\text{vec}(\mathcal{D}_{\text{mat}})^{\perp}$. Therefore, there exists a parity-check matrix for $\text{vec}(\mathcal{D}_{\text{mat}})$ of the form

$$ \mathbf{H} = \begin{pmatrix} \mathbf{U} \\ \mathbf{H}_{\sigma} \end{pmatrix}, $$

where the rows of $\mathbf{H}_{\sigma} \in \mathbb{F}_{q^k}^{\binom{k}{2} \times k^2}$ are the $\sigma_{i,j}$ and $\mathbf{U} \in \mathbb{F}_{q^k}^{(k^2 - 2k - \binom{k}{2}) \times k^2}$. The equations coming from $\mathbf{H}_{\sigma} \text{vec}(\mathbf{X})^{\top} = 0$ all give the zero polynomial. Therefore, the useful part of the system is given by

$$ \mathbf{U} \text{vec}(\mathbf{X})^{\top} = 0, $$

and it contains $k^2 - 2k - \binom{k}{2}$ equations. $\square$

**Modeling 1 (Parity-check modeling over $\mathbb{F}_{q^k}$)** Let $\mathbf{X}$ be the matrix of unknowns defined in Equation (15), let $n = 2k$ and let $\mathbf{H} = \begin{pmatrix} \mathbf{U} \\ \mathbf{H}_{\sigma} \end{pmatrix} \in \mathbb{F}_{q^k}^{(k^2-n) \times k^2}$ be a parity-check matrix for the code $\text{vec}(\mathcal{D}_{\text{mat}})$ as described in the proof of Lemma 2, where $\mathcal{D}_{\text{mat}} = \mathcal{C}_{\text{mat}} \cap \mathbb{F}_{q^k}^{k \times k}$. We consider the system $\mathcal{F}$ over $\mathbb{F}_{q^k}$ given by

$$ \mathbf{U} \text{vec}(\mathbf{X})^{\top} = 0. \qquad (17) $$

This system contains $k^2 - n - \binom{k}{2}$ quadratic equations in the $x_i$ variables.

It is readily verified that the solutions to Modeling 1 are in one-to-one correspondence with the elements of $\mathbb{Z}_{\mathbb{F}_{q^k}}$. Experimentally, these solutions were also all of the form described in Proposition 2. If one wants to find an element in $\mathbb{Z}_{\mathbb{F}_{q^k}}$ in practice, two variables must be fixed in Modeling 1 to obtain a zero-dimensional ideal. The corresponding variety over $\mathbb{F}_{q^k}$ has size $\ge k$ still by using Proposition 2, and experimentally this was always an equality.
**Modeling 2 (Recovering an element in $\mathbb{Z}_{\mathbb{F}_q}^k$)** Let $(s, t) \in \mathbb{R}_{q^k}^2$ such that $t \notin \langle s \rangle_{\mathbb{F}_q}$. We consider the system $\mathcal{F}_{spec}$ obtained by fixing $x_{k-1} = s$ and $x_k = t$ in the equations of the sequence $\mathcal{F}$ from Modeling 1.

The approach that we use to solve this system $\mathcal{F}_{spec}$ is standard. We start by computing a Gröbner basis for a suitable ordering and then we perform a change of order step to deduce a basis for the lexicographic ordering to get the solutions. Using Proposition 2, we expect $k$ distinct solutions to Modeling 2, and therefore the complexity of this second step is polynomial in $k$ by using the so-called FGLM algorithm [14]. In the following, we will focus on the complexity of the first step.

## 4.2 Complexity of solving the system $\mathcal{F}_{spec}$.

In this section, we show that, under the following Assumption 1 and Assumption 2, the system $\mathcal{F}_{spec}$ can always be solved at degree 3 independently from the value of $k$.

First, note that one can permute the coordinates of the row-vector $\text{vec}(\mathbf{X})$ and the columns of $\mathbf{U}$ accordingly so that the $\binom{k+1}{2}$ leftmost entries of $\text{vec}(\mathbf{X})$ correspond to all the distinct monomials $x_i x_j$ for $1 \le i \le j \le k$. This is equivalent to choosing a grevlex ordering on the $x_i$ variables to label the columns of $\mathbf{U}$. Also, by adding rows of $\mathbf{H}_\sigma$ to rows of $\mathbf{U}$ in $\mathbf{H}$, it is always possible to assume that the last $\binom{k}{2}$ columns of the matrix $\mathbf{U}$ are identically zero.

**Assumption 1** We assume that $\mathbf{U}$ is full-rank, and moreover we assume that the submatrix $\mathbf{U}_{*,\{1..(\binom{k-1}{2})\}}$ is also full-rank.

The first part of Assumption 1 ensures that one can find $\binom{k-1}{2}$ distinct leading monomials of the form $x_i x_j$ for $1 \le i \le j \le k$ in the $\mathbb{F}_q$-span of the polynomials $\mathcal{F}$, and a fortiori the equations from Modeling 1 are linearly independent. The second part is a bit stronger: it implies that these leading monomials will not involve $x_{k-1}$ or $x_k$. Therefore, by doing linear combinations between the equations from the specialized system $\mathcal{F}_{spec}$, one can obtain a set $\mathcal{G}_{spec}$ of $m := k^2 - 2k - \binom{k}{2} = \frac{k^2-3k}{2}$ equations $g_1 = 0, \dots, g_m = 0$ with distinct leading monomials $x_i x_j$ for $1 \le i, j \le k-2$. Since the total number of quadratic monomials of this form is equal to

$$ \binom{k-1}{2} = \frac{(k-1)(k-2)}{2} = \frac{k^2 - 3k}{2} + 1, $$

this implies that all monomials of degree 2 appear as leading terms of the $g_i$'s but one. With this assumption it can be proved that computing the Gröbner basis of the algebraic system $\mathcal{F}_{spec}$ is extremely efficient: essentially it amounts to compute the aforementioned echelonized set of quadratic polynomials $\mathcal{G}_{spec}$, and then the Gröbner basis is either already computed or close to be computed. This is easily verified by making the further assumption that
**Assumption 2** The algebraic system $\mathcal{F}_{spec}$ has exactly $k$ distinct solutions which do not belong to a common hyperplane of $\mathbb{F}_{q^k}^{k-2}$.

This assumption was satisfied in all our experiments and is natural when considering Proposition 2 together with Observation 2, which suggests that the inclusion given in this Proposition is an equality. Indeed, the form of the solutions we get from this Proposition then suggests that Assumption 2 should typically hold.

Buchberger's algorithm for computing a Gröbner basis from $\mathcal{G}_{spec} = \{g_1 = 0, \dots, g_m = 0\}$ would start by computing the $S$-polynomials $S(g_i, g_j)$ and reduce them. There are two cases to consider.

**Case 1.** The missing leading monomial in the $g_i$'s is of the form $x_i x_j$. Note that the only case where $S(g_i, g_j)$ were not reduced to 0 would be when the leading monomials of $g_i$ and $g_j$ have a common factor (see [10, Prop. 4, p.106]). In such a case, the polynomial $S(g_i, g_j)$ is of degree at most 3 and since in our situation (i) all the monomials of degree 3 appear as multiples of leading monomials of the $g_i$'s,

(ii) all monomials of degree 2 appear as leading monomials in the $g_i$'s but $x_i x_j$, this implies that $S(g_i, g_j)$ is reduced to a polynomial of the form $g_{m+1} := \mu x_i x_j + L(\mathbf{x})$ where $L$ is affine in the $x_i$'s. It is impossible that $\mu = 0$ and $L \neq 0$ since this would imply that all the $k$ solutions to $\mathcal{F}_{spec}$ lie in the affine hyperplane $L(\mathbf{x}) = 0$, which contradicts Assumption 2. If $\mu \neq 0$, then it is clear by performing the same reasoning that all $S$-polynomials $S(g_{m+1}, g_i)$ would reduce to 0 (since they would this time reduce to affine forms which are necessarily 0 by the previous reasoning). We are therefore left with a Gröbner basis.

**Case 2.** The missing leading monomial in the $g_i$'s is of the form $x_i^2$. The difference with the previous case is that all degree 3 monomials appear as multiples of leading monomials of the $g_i$'s with the exception of $x_i^3$. In such a case, $S(g_i, g_j)$ reduces to a polynomial of the form $g_{m+1} := \lambda x_i^3 + \mu x_i^2 + L(\mathbf{x})$ where $L$ is again an affine form. It is readily seen that we can not have $\lambda = \mu = 0$ without that $L = 0$ itself (this would contradict in the same way as before Assumption 2). From this, it is readily seen that all $S$-polynomials $S(g_{m+1}, g_j)$ reduce to 0 and that we have a Gröbner basis again.

**Remark 1** Actually the first part of Assumption 2 is already enough to prove this kind of behavior for the Gröbner basis computation by using the fact that the number of solutions for $\mathcal{G}_{spec}$ is equal to the number of monomials that can not be leading monomials of an element of the ideal generated by the $g_i$'s (this is essentially a corollary of [15, Cor. 5, p.83]). We have avoided to use this result to keep the proof as simple as possible. The constant monomial is an example of such a kind (because $\mathcal{G}_{spec}$ has solutions), there are at most $k-2$ monomials of degree 1, at most one monomial of degree 2 and at most one monomial of degree 3 of such kind. From this, it is for instance straightforward to rule out the possibility that $g_{m+1} \neq 0$ in Case 1.

Overall, one needs to go up to degree 3 in the worst case to compute the Gröbner basis for $\mathcal{F}_{spec}$. The final complexity is then dominated by that of
performing Gaussian elimination at degree 3 on a matrix of size $A \times B$ with
$A \le B := \binom{k-2+3}{3}$, say

$$
\mathcal{O}\left(\binom{k-2+3}{3}^{\omega}\right) \qquad (18)
$$

operations in $\mathbb{F}_q$, where $2 \le \omega \le 3$ is the linear algebra constant. Therefore,
the complexity of solving the system is in $\mathcal{O}(k^{3\omega})$, which is clearly polynomial
in the dimension $k$ of the Sidon space.

5 Finding an equivalent Sidon space V'.

Even if recovering elements in Z$_{F_q}$ can be performed in an efficient way, it
remains to explain how this leads to a key-recovery attack. In particular, we
have yet to show how we obtain from those elements an equivalent key. We will
prove here that we obtain from a set of $k + 1$ elements $t_1, \dots, t_{k+1}$ in Z$_{F_q}$ a
Sidon space V' obtained by Construction 1 that meets the criterion of Fact 1,
namely that there is an ordered basis v' for it such that M(v') lies in the space
spanned by the M(i)'s. This procedure consists in

1. From $t_1, \dots, t_{k+1}$ in $\mathbb{Z}_{\mathbb{F}_{q^k}}$ we recover $\mathbf{t} = \lambda \mathbf{u}^{[j]}$ for some $\lambda \in \mathbb{F}_{q^k}$ and $j$ in $\{0, \dots, k-1\}$ where $\mathbf{u} = (u_1, \dots, u_k)$ is defined from the secret basis $\mathbf{v}$ of the Sidon space of the scheme by (10).

2. From such a **t**, we deduce the aforementioned Sidon space **V**' as

$$
\mathcal{V}' = \langle t_1 + \gamma' t_1^q, \dots, t_k + \gamma' t_k^q \rangle_{\mathbb{F}_q},
$$

where $(t_1, \dots, t_k) = \mathbf{t}$ and $\gamma'$ is an element generated like $\gamma$ in **Keygen**,
namely as a root of an irreducible polynomial $x^2 + ex + f$ over $\mathbb{F}_{q^k}$ such that
$f \in \overline{W_{q-1}}$.

5.1 Targeting an element of the form $\lambda u^{[j]}$.

Assuming that the inclusion in Proposition 2 is an equality, one obtains that the
set $\mathbb{Z}_{\mathbb{F}_{q^k}}$ is equal to the union of vector spaces

$$
\mathbb{Z}_{\mathbb{F}_{q^k}} = \bigcup_{i=1}^{k} \mathcal{W}_i, \quad \text{where} \quad \mathcal{W}_i := \langle \mathbf{u}^{[i-1]}, \mathbf{u}^{[i]} \rangle_{\mathbb{F}_{q^k}}.
$$

Let us notice that these vector spaces $\mathcal{W}_i$ satisfy a peculiar property, namely
that

$$
\mathcal{W}_i \cap \mathcal{W}_i^{[1]} = \langle \mathbf{u}^{[i]} \rangle \qquad (19)
$$

where for a set $S$ of vectors, $S^{[1]}$ stands for the set $\{\mathbf{x}^{[1]} : \mathbf{x} \in S\}$. (19) follows
from the fact that $\mathcal{W}_i^{[1]}$ is the $\mathbb{F}_{q^k}$-vector space generated by $\mathbf{u}^{[i]}$ and $\mathbf{u}^{[i+1]}$. In
other words, we are able to recover one of the $\mathbf{u}^{[i]}$'s up to multiplication by an
element of $\mathbb{F}_{q^k}$ if we are able to produce one of those $W_i$'s. This can be achieved
by using the pigeonhole principle: two among the solutions $\mathbf{t}_i$ for $1 \le i \le k+1$
will fall into a same vector space $W_{j_0}$. These considerations lead to the following
procedure for recovering one of those $\mathbf{u}^{[i]}$'s (up to a multiplicative constant)

**Input:** A set of $k+1$ non-collinear vectors $\mathbf{t}_1, \dots, \mathbf{t}_{k+1}$ in $\mathcal{Z}_{\mathbb{F}_{q^k}}$.

**Output:** A set $S$ of elements containing at least one element collinear with one of the $\mathbf{u}^{[i]}$'s.

for $i = 1$ to $k$ do

| for $j = i$ to $k+1$ do
| $V \leftarrow \langle \mathbf{t}_i, \mathbf{t}_j \rangle_{\mathbb{F}_{q^k}}$
| **if** $\dim V \cap V^{[1]} = 1$ **then**
| $S \leftarrow S \cup \{\mathbf{x}\}$ // where $\mathbf{x}$ generates $V \cap V^{[1]}$
| **end**
| end
end

This algorithm is of complexity $O(k^2)$ and it remains now just to explain
how from one of those elements of $S$ which is collinear with a $\mathbf{u}^{[i]}$ we are able
to produce an equivalent key for the Sidon cryptosystem. Notice that we do not
even need to have $k+1$ non-collinear vectors $\mathbf{t}_1, \dots, \mathbf{t}_{k+1}$ in $\mathbb{F}_{q^k}$, $\Theta(\sqrt{k})$ vectors
are indeed sufficient by using the birthday paradox to get an $S$ containing an
element $\mathbf{t}$ collinear with some $\mathbf{u}^{[i]}$ with probability $\Omega(1)$.

## 5.2 Deducing $\mathcal{V}'$ from $\mathbf{t}$

How a Sidon space $\mathcal{V}'$ with the right properties can be deduced from $\mathbf{t}$ collinear
with some $\mathbf{u}^{[i]}$ is explained by the following proposition.

**Proposition 3** Let $\gamma'$ be a root of an irreducible polynomial $x^2 + ex + f$ over $\mathbb{F}_{q^k}$ such that $f \in \bar{W}_{q-1}$. Then, the $\mathbb{F}_q$-linear space $\mathcal{V}'$ generated by the ordered basis $\mathbf{v}' := \mathbf{t} + \gamma' \mathbf{t}^{[1]}$ is a Sidon space $\mathcal{V}'$ such that $\mathbf{M}(\mathbf{v}')$ is spanned by the $\mathbf{M}_i$'s.

*Proof.* We have

$$
\begin{align*}
\mathbf{M}(\boldsymbol{\nu}') &= \mathbf{M}(\mathbf{t} + \gamma' \mathbf{t}^{[1]}) \\
&= \mathbf{t}^{\top} \mathbf{t} + \gamma'^2 (\mathbf{t}^{[1]})^{\top} \mathbf{t}^{[1]} + \gamma' \mathbf{t}^{\top} \mathbf{t}^{[1]} + \gamma' (\mathbf{t}^{[1]})^{\top} \mathbf{t} \\
&= \lambda^2 \mathbf{u}^{\top} \mathbf{u} + \lambda^{2q} \gamma'^2 (\mathbf{u}^{[1]})^{\top} \mathbf{u}^{[1]} + \lambda^{1+q} \gamma' \left\{ \mathbf{u}^{\top} \mathbf{u}^{[1]} + (\mathbf{u}^{[1]})^{\top} \mathbf{u} \right\} \quad \text{(since } \mathbf{t} = \lambda \mathbf{u} \text{ for } \lambda \in \mathbb{F}_{q^k}) \\
&= \lambda^2 \mathbf{M}(\mathbf{u}) + \lambda^{2q} \gamma'^2 \mathbf{M}(\mathbf{u}^{[1]}) + \lambda^{1+q} \gamma' \left\{ (\mathbf{u} + \mathbf{u}^{[1]})^{\top} (\mathbf{u} + \mathbf{u}^{[1]}) - \mathbf{u}^{\top} \mathbf{u} - (\mathbf{u}^{[1]})^{\top} \mathbf{u}^{[1]} \right\} \\
&= \lambda^2 \mathbf{M}(\mathbf{u}) + \lambda^{2q} \gamma'^2 \mathbf{M}(\mathbf{u}^{[1]}) + \lambda^{1+q} \gamma' \left\{ \mathbf{M}(\mathbf{u} + \mathbf{u}^{[1]}) - \mathbf{M}(\mathbf{u}) - \mathbf{M}(\mathbf{u}^{[1]}) \right\} \\
&\in \langle \mathbf{M}^{(1)}, \dots, \mathbf{M}^{(n)} \rangle_{\mathbb{F}_{q^n}} \quad \text{(by Proposition 2).}
\end{align*}
$$
□

In other words for finding $V'$, we just have to

1. find an element $\gamma'$ satisfying the same constraints as $\gamma$, i.e. $\gamma'$ is a root of an irreducible polynomial $x^2 + ex + f$ over $\mathbb{F}_{q^k}$ such that $f \in \overline{W}_{q-1}$;

2. $V'$ is then generated by the basis

$$ \nu' = \{t_1 + \gamma't_1^q, \dots, t_k + \gamma't_k^q\} $$

and leads to an equivalent key by Fact 1.

Note that Step 1. for finding $\gamma' \in \mathbb{F}_{q^n}$ can be performed in the same way as in **Keygen**. This was done at random in [22], and the success probability can be estimated using [23, Lemma 13]. Heuristically, this works in constant expected time.

# 6 Conclusion.

The use of Sidon spaces for cryptography is an interesting new idea initially proposed in [22]. However, in this paper we show that this first attempt to build a public-key encryption scheme based on Sidon spaces is insecure. Here, we develop a key-recovery attack which is polynomial in the dimension of the underlying Sidon space. Besides of that, we consider worth to further study the possibility of using Sidon spaces to devise other cryptographic primitives.

# Acknowledgements

The authors would like to thank Magali Bardet for her valuable comments to improve the quality of this paper.

# References

1. Daniel Apon, Dustin Moody, Ray Perlner, Daniel Smith-Tone, and Javier Verbel. Combinatorial rank attacks against the rectangular simple matrix encryption scheme. In Jintai Ding and Jean-Pierre Tillich, editors, *Post-Quantum Cryptography*, pages 307–322, Cham, 2020. Springer International Publishing.

2. Christine Bachoc, Oriol Serra, and Gilles Zémor. An analogue of Vosper's theorem for extension fields. *Mathematical Proceedings of the Cambridge Philosophical Society*, 163(3):423–452, November 2017.

3. Magali Bardet, Maxime Bros, Daniel Cabarcas, Philippe Gaborit, Ray Perlner, Daniel Smith-Tone, Jean-Pierre Tillich, and Javier Verbel. Improvements of algebraic attacks for solving the rank decoding and minrank problems. In Shiho Moriai and Huaxiong Wang, editors, *Advances in Cryptology – ASIACRYPT 2020*, pages 507–536, Cham, 2020. Springer International Publishing.

4. Luk Bettale, Jean-Charles Faugère, and Ludovic Perret. Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic. *Designs, Codes and Cryptography*, 69(1):1–52, 2013.
5. Pierre Briaud and Javier Verbel. Cryptanalysis tool for the sidon cryptosystem, 2021. https://github.com/Javierverbel/cryptanalysis-sidon-cryptosystem.

6. Jonathan F. Buss, Gudmund S. Frandsen, and Jeffrey O. Shallit. The computational complexity of some problems of linear algebra. *J. Comput. System Sci.*, 58(3):572–596, June 1999.

7. Daniel Cabarcas, Daniel Smith-Tone, and Javier Verbel. Key recovery attack for zhfe. In Tanja Lange and Tsuyoshi Takagi, editors, *Post-Quantum Cryptography*, pages 289–308, Cham, 2017. Springer International Publishing.

8. Ryann Cartor and Daniel Smith-Tone. EFLASH: A new multivariate encryption scheme. In *Selected Areas in Cryptography - SAC 2018 - 25th International Conference, Calgary, AB, Canada, August 15-17, 2018, Revised Selected Papers*, pages 281–299, 2018.

9. Antoine Casanova, Jean-Charles Faugère, Gilles Macario-Rat, Jacques Patarin, Ludovic Perret, and Jocelyn Ryckeghem. GeMSS: A Great Multivariate Short Signature. Research report, UPMC - Paris 6 Sorbonne Universités ; INRIA Paris Research Centre, MAMBA Team, F-75012, Paris, France ; LIP6 - Laboratoire d'Informatique de Paris 6, December 2017.

10. David A. Cox, John Little, and Donal O'Shea. *Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3/e (Undergraduate Texts in Mathematics)*. Springer-Verlag New York, Inc., Se-caucus, NJ, USA, 2007.

11. Thomas Debris-Alazard and Jean-Pierre Tillich. Two attacks on rank metric code-based schemes: Ranksign and an identity-based-encryption scheme. In *Advances in Cryptology - ASIACRYPT 2018*, LNCS, pages 62–92, Brisbane, Australia, December 2018. Springer.

12. Jintai Ding. Rainbow. Second round submission to the NIST post-quantum cryptography call, April 2019.

13. Jean-Charles Faugère, Mohab Safey El Din, and Pierre-Jean Spaenlehauer. Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology. In *International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, Munich, Germany, July 25-28, 2010*, pages 257–264, 2010.

14. J.C. Faugère, P. Gianni, D. Lazard, and T. Mora. Efficient computation of zero-dimensional gröbner bases by change of ordering. *Journal of Symbolic Computation*, 16(4):329 – 344, 1993.

15. Ralf Fröberg. *An introduction to Gröbner bases*. Pure and applied mathematics. Wiley, 1998.

16. Louis Goubin and Nicolas Courtois. Cryptanalysis of the TTM cryptosystem. In Tatsuaki Okamoto, editor, *Advances in Cryptology - ASIACRYPT 2000*, volume 1976 of LNCS, pages 44–57. Springer, 2000.

17. Yasuhiko Ikematsu, Ray A. Perlner, Daniel Smith-Tone, Tsuyoshi Takagi, and Jeremy Vates. HFERP - A new multivariate encryption scheme. In *Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings*, pages 396–416, 2018.

18. Dustin Moody, Ray A. Perlner, and Daniel Smith-Tone. Key recovery attack on the cubic ABC simple matrix multivariate encryption scheme. In *Selected Areas in Cryptography - SAC 2016 - 23rd International Conference, St. John's, NL, Canada, August 10-12, 2016, Revised Selected Papers*, pages 543–558, 2016.

19. Morten Øygarden, Patrick Felke, Hävard Raddum, and Carlos Cid. Cryptanalysis of the multivariate encryption scheme eflash. In Stanislaw Jarecki, editor, *Topics in Cryptology - CT-RSA 2020*, pages 85–105, Cham, 2020. Springer International Publishing.
20. Jacques Patarin. Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. In *EUROCRYPT*, pages 33–48, 1996.

21. Jaiberth Porras, John Baena, and Jintai Ding. Zhfe, a new multivariate public key encryption scheme. In Michele Mosca, editor, *Post-Quantum Cryptography*, pages 229–245, Cham, 2014. Springer International Publishing.

22. Netanel Raviv, Ben Langton, and Itzhak Tamo. Multivariate public key cryptosystem from sidon spaces. In Juan A. Garay, editor, *Public-Key Cryptography – PKC 2021*, pages 242–265, Cham, 2021. Springer International Publishing.

23. Ron M. Roth, Netanel Raviv, and Itzhak Tamo. Construction of Sidon spaces with applications to coding. *IEEE Transactions on Information Theory*, 64(6):4412–4422, 2018.

24. Daniel Smith-Tone and Javier A. Verbel. A rank attack against extension field cancellation. In Jintai Ding and Jean-Pierre Tillich, editors, *Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020, Paris, France, April 15-17, 2020, Proceedings*, volume 12100 of *Lecture Notes in Computer Science*, pages 381–401. Springer, 2020.

25. Alan Szepieniec, Jintai Ding, and Bart Preneel. Extension field cancellation: A new central trapdoor for multivariate quadratic systems. In Tsuyoshi Takagi, editor, *Post-Quantum Cryptography*, pages 182–196, Cham, 2016. Springer International Publishing.

26. Chengdong Tao, Adama Diene, Shaohua Tang, and Jintai Ding. Simple matrix scheme for encryption. In *PQCrypto*, pages 231–242, 2013.