# Recent algebraic attacks on the McEliece cryptosystem

Jean-Pierre Tillich

► To cite this version:

Jean-Pierre Tillich. Recent algebraic attacks on the McEliece cryptosystem. PQCrypto 2023, Gorjan Alagic, Andrew Childs, Dustin Moody, Rene Peralta, Angela Robinson, Aug 2023, College Park, United States. hal-04276650

HAL Id: hal-04276650

https://inria.hal.science/hal-04276650v1

Submitted on 9 Nov 2023

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

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

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Recent algebraic attacks on the McEliece
cryptosystem

J.-P. Tillich (Inria de Paris)

June 21, 2023
Joint work

► “On the dimension and structure of the square of the dual of a Goppa code”, R. Mora, J.-P. Tillich, *Designs, Codes and Cryptography*, 2022

► “Polynomial time key-recovery attack on high rate random alternant codes”, M. Bardet, R. Mora, J.-P. Tillich, https://arxiv.org/abs/2304.14757

► “A new approach based on quadratic forms to attack the McEliece cryptosystem”, A. Couvreur, R. Mora, J.-P. Tillich, https://eprint.iacr.org/2023/950
# 1. The McEliece cryptosystem

* **1978 McEliece cryptosystem based on Goppa codes.**

* **Secret Key:** The algebraic structure of an $[n, k]_q$ Goppa code $C$ which has an efficient decoding algorithm for decoding $t$ errors

* **Public Key:** an arbitrary generator matrix $G$ of $C$.

* **Encryption:** $m \in \mathbb{F}_q^k \mapsto y \stackrel{\text{def}}{=} mG + e$ with $|e| = t$.

* **Decryption:** $y \mapsto m = \text{Decode}(y)$.
# Advantages/drawbacks

## Advantages

* Post Quantum, 4th-round finalist of the NIST competition;

* 55 years of research have not changed much the picture

> Compl. of key attacks $\gg$ Compl. of message attacks $\approx 2^{\alpha n}$
> with $\alpha \approx$ Constant

* Efficient encryption and decryption

## Drawbacks

* Huge size of the keys, Classic McEliece $\approx$ 260 Kbytes.
# Key Attacks/Message Attacks (pre 2011)

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

* **Key attack:** (pre 2011) Enumerating all Goppa polynomial + solving the code-equivalence problem

* **Message attack:** Decoding a generic linear code
# Key Attacks/Message Attacks (2011)

* Distinguishing Attack
  [Faugère-Gauthier-Otmani-Perret-Tillich-2011]: distinguishing a
  Goppa/alternant code from a generic linear code

* $n-k = \Theta(n)$

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

* $n-k = O(n^{\frac{1}{2}})$

<figure><img src="image_4.png" /></figure>
# Key Attacks/Message Attacks [BMT23]

## Assumptions:

1. the code should be distinguishable (⇒ $n-k = O(n^{\frac{1}{2}})$) with the method of [FGOPT11]

2. should be a generic alternant code rather than a Goppa code

3. $q \in \{2, 3\}$

<figure><img src="image_5.png" /></figure>
# A new approach and a new distinguisher [CMT23]

* Associating a space of quadratic forms to an alternant/Goppa code and looking for low rank quadratic forms in it by Gröbner basis techniques

⇒ a new distinguisher in characteristic 2

$$s \stackrel{\text{def}}{=} n-k$$

$$n = s^{\alpha}$$

$$\alpha \in (1,2)$$

<figure><img src="image_6.png" /></figure>
# A new approach and a new attack [CMT23]

## Assumption:

* Generic alternant and distinguishable [FGOPT11] codes
or

* distinguishable [FGOPT11] Goppa codes with
  $\deg(\text{Goppa polynomial}) < q - 1$

<figure><img src="image_7.png" /></figure>
2.Alternant and Goppa Codes
Generalized Reed-Solomon codes

**Definition 1.** [**Generalized Reed-Solomon code**] $k$ and $n$ integers with $1 \le k < n \le q$ where $q$ is a power of a prime number. The generalized Reed-Solomon code $\text{GRS}_k(x, y)$ of dimension $k$ associated to a pair $(x, y) \in \mathbb{F}_q^n \times \mathbb{F}_q^n$ where $x$ is an $n$-tuple of distinct elements of $\mathbb{F}_q$ and the entries $y_i$ are arbitrary nonzero elements in $\mathbb{F}_q$ is defined as:

$$ \text{GRS}_k(x, y) \stackrel{\text{def}}{=} \{ (y_1p(x_1), \dots, y_np(x_n)) : p \in \mathbb{F}_q[X], \deg p < k \}. $$

$x$ is the **support** and $y$ the **multiplier**.

**[Sidelnikov-Shestakov1992]**: recover from an arbitrary generator matrix of a GRS code $C$, a tuple $(x, y)$ such that $C = \text{GRS}(x, y)$ (all what is needed to decode $C$ efficiently).
Alternant codes

**Definition 1.** [alternant/Goppa code] $\boldsymbol{x} \in \mathbb{F}_{q^m}^n, \boldsymbol{y} \in \mathbb{F}_{q^m}^n$ as in def. of GRS codes, $\Gamma \in \mathbb{F}_{q^m}[z]$, $\deg \Gamma = r$. The alternant code $\text{Alt}_r(\boldsymbol{x}, \boldsymbol{y})$, resp. Goppa code $\text{Gop}(\boldsymbol{x}, \Gamma)$ of support $\boldsymbol{x}$, degree $r$ and extension degree $m$ are defined by

$$ \text{Alt}_r(\boldsymbol{x}, \boldsymbol{y}) \stackrel{\text{def}}{=} \text{GRS}_r(\boldsymbol{x}, \boldsymbol{y})^{\perp} \cap \mathbb{F}_q^n \\ = \text{GRS}_{n-r}(\boldsymbol{x}, \boldsymbol{y}^{\perp}) \cap \mathbb{F}_q^n \text{ (subfield subcode of GRS)} $$

$$ \text{Gop}(\boldsymbol{x}, \Gamma) = \text{Alt}_r(\boldsymbol{x}, \frac{1}{\Gamma(\boldsymbol{x})}) $$

$$ \text{GRS}_r(\boldsymbol{x}, \boldsymbol{y})^{\perp} = \text{GRS}_{n-r}(\boldsymbol{x}, \boldsymbol{y}^{\perp}) $$

$$ \boldsymbol{y}^{\perp} \stackrel{\text{def}}{=} \left( \frac{1}{y_i \pi_x'(x_1)}, \dots, \frac{1}{y_i \pi_x'(x_1)} \right) $$

$$ \pi_x(\boldsymbol{x}) \stackrel{\text{def}}{=} (x - x_1) \cdots (x - x_n) $$
3. The square code

► Key ingredient for the [FGOPT11]/[MT22] distinguisher and the
[BMT23] attack

► Introduced for cryptanalyzing the Berger-Loidreau scheme by
Wieschebrink in 2010
The square code

**Definition 2. [Componentwise product]** Given two vectors $\mathbf{a} = (a_1, \dots, a_n)$ and $\mathbf{b} = (b_1, \dots, b_n) \in \mathbb{F}_q^n$, we denote by $\mathbf{a} \star \mathbf{b}$ the componentwise product

$$ \mathbf{a} \star \mathbf{b} \stackrel{\text{def}}{=} (a_1 b_1, \dots, a_n b_n) $$

**Definition 3. [Product of codes & square code]** The star product code denoted by $\mathcal{A} \star \mathcal{B}$ of $\mathcal{A}$ and $\mathcal{B}$ is the vector space spanned by all products $\mathbf{a} \star \mathbf{b}$ where $\mathbf{a}$ and $\mathbf{b}$ range over $\mathcal{A}$ and $\mathcal{B}$ respectively. When $\mathcal{B} = \mathcal{A}$, $\mathcal{A} \star \mathcal{A}$ is called the square code of $\mathcal{A}$ and is rather denoted by $\mathcal{A}^2$.
Dimension of the square code

A and B codes with respective bases ($\mathbf{a}_i$) and ($\mathbf{b}_j$).

$$
1. \dim(\mathcal{A} \star \mathcal{B}) \le \dim(\mathcal{A}) \dim(\mathcal{B}) \text{ (generated by the } \mathbf{a}_i \star \mathbf{b}_j \text{'s)}
$$

$$
2. \dim(\mathcal{A}^2) \le \left( \dim(\mathcal{A}) + 1 \right) \text{ (generated by the } \mathbf{a}_i \star \mathbf{a}_j \text{'s with } i \le j)
$$
# What is wrong with generalized Reed-Solomon codes ?

When $\mathcal{C}$ is a random code of length $n$, with high probability

$$ \dim(\mathcal{C}^2) = \min \left\{ \binom{\dim(\mathcal{C}) + 1}{2}, n \right\} $$

When $\mathcal{C}$ is a generalized Reed-Solomon code

$$ \dim(\mathcal{C}^2) = \min \{2 \dim(\mathcal{C}) - 1, n\} $$
The explanation

$\mathbf{c} = (y_1p(x_1), \dots, y_np(x_n))$, $\mathbf{c}' = (y_1q(x_1), \dots, y_nq(x_n)) \in \mathbf{GRS}_k(\mathbf{x}, \mathbf{y})$ where $p$ and $q$ are two polynomials of degree at most $k-1$.

$\mathbf{c} \star \mathbf{c}' = (y_1^2p(x_1)q(x_2), \dots, y_n^2p(x_n)q(x_n)) = (y_1^2r(x_1), \dots, y_n^2r(x_n))$ where $r$ is a polynomial of degree $\le 2k-2$.

$$ \implies \mathbf{c} \star \mathbf{c}' \in \mathbf{GRS}_{2k-1}(\mathbf{x}, \mathbf{y}^2) $$
# What happens for alternant/Goppa codes
## [FGOPT11][MT22]?

Alternant/Goppa code $\mathcal{C}$ over $\mathbb{F}_q$ of length $n$, degree $r$, ext. deg. $m$

$$ \dim \mathcal{C}^{\perp} \stackrel{\text{typ.}}{=} rm $$

$$ \dim \left( \left( \mathcal{C}_{\text{Gop}}^{\perp} \right)^2 \right) \le \dim \left( \left( \mathcal{C}_{\text{alt}}^{\perp} \right)^2 \right) $$

$$ \dim \left( \left( \mathcal{C}^{\perp} \right)^2 \right) \le \min \left( n, \underbrace{\binom{mr+1}{2}}_{\dim \mathcal{R}^2} - \Omega(mr^2 \log r) \right) $$

$$ \mathcal{R} \stackrel{\text{def}}{=} \text{random code of length } n, \text{ dim } rm $$
4. [BMT23] : filtration attack + Gröbner bases

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

► Transforming the distinguisher into an attack
A theorem

C a code of length $n$, $I, J \subset \{1, \dots, n\}$

$$ \boldsymbol{x}_J = (x_j)_{j \in J} $$

$$ \boldsymbol{x}_{\setminus I} = (x_j)_{j \notin I} $$

$$ \text{Shortened code } \mathbf{Sh}_I(C) = \{ \boldsymbol{c}_I : \boldsymbol{c} \in c_i = 0, \forall i \in I \} $$

**Theorem 1. [BMT23]** Let $\mathbf{Alt}_r(\boldsymbol{x}, \boldsymbol{y})$ be an alternant code on $\mathbb{F}_q$ such that $r \ge q+1$ and let $C \stackrel{\text{def}}{=} \mathbf{Alt}_r(\boldsymbol{x}_{\setminus i}, \boldsymbol{y}_{\setminus i})^{\perp}$, $D \stackrel{\text{def}}{=} (\mathbf{Sh}_i(\mathbf{Alt}_r(\boldsymbol{x}, \boldsymbol{y})^{\perp}))^2$, then

$$ C \star \mathbf{Alt}_{r-1}(\boldsymbol{x}_{\setminus i}, \boldsymbol{y}_{\setminus i}(\boldsymbol{x}_{\setminus i} - \boldsymbol{x}_i))^{\perp} \subseteq D $$
Filtration

► For given subspaces $\mathcal{A}$ and $\mathcal{B}$, computing the largest subspace $\mathcal{X}$ such that

$$ \mathcal{A} \star \mathcal{X} \subseteq \mathcal{B} $$

is just solving a linear system.

**Conjecture 1.** For $r \ge q+1$ and if $(\mathrm{Sh}_i (\mathrm{Alt}_r (\mathbf{x}, \mathbf{y})^{\perp}))^2$ is not the full space. Let $\mathcal{X}$ be largest subspace such that $\mathcal{C} \star \mathcal{X} \subset \mathcal{D}$. Then for a generic alternant code

$$ \mathcal{X} = \mathrm{Alt}_{r-1}(\mathbf{x}_{\setminus i}, \mathbf{y}_{\setminus i}(\mathbf{x}_{\setminus i} - \mathbf{x}_i))^{\perp} $$

For a Goppa code $\mathrm{Alt}_{r-1}(\mathbf{x}_{\setminus i}, \mathbf{y}_{\setminus i}(\mathbf{x}_{\setminus i} - \mathbf{x}_i))^{\perp} \subset \mathcal{X}$
Filtration (ii)+attack

► $\mathbf{Alt}_r(x, y) \to \mathbf{Alt}_{r-1}(x \setminus i, \dots)^\perp \to \dots \to \mathbf{Alt}_q(x \setminus I, \dots)^\perp$

► The support $x$ and multiplier $y$ of an alternant code $\mathbf{Alt}_r(x, y)$
can be recovered **efficiently** by a suitable algebraic modeling +
Gröbner bases techniques when $r = 3 \Rightarrow$

efficient attack when $q \in \{2, 3\}$
GRS codes

$$ \begin{aligned} \mathcal{C} &\stackrel{\text{def}}{=} \mathbf{GRS}_k(\mathbf{x}_{\setminus i}, \mathbf{y}_{\setminus i}) \\ &= \{(y_j P(x_j))_{j \neq i} : \deg P \leq k-1\} \end{aligned} $$

$$ \begin{aligned} \mathcal{D} &\stackrel{\text{def}}{=} (\mathbf{Sh}_i(\mathbf{GRS}_k(\mathbf{x}, \mathbf{y})))^2 \\ &= \{(y_j(x_j - \mathbf{x}_i)^2 P(x_j))_{j \neq i} : \deg P \leq 2k-4\} \text{ since} \end{aligned} $$

$$ \mathbf{Sh}_i(\mathbf{GRS}_k(\mathbf{x}, \mathbf{y})) = \{(y_j(x_j - \mathbf{x}_i)P(x_j))_{j \neq i} : \deg P \leq k-2\} $$

$$ \begin{aligned} \mathcal{X} &= \mathbf{GRS}_{k-2}(\mathbf{x}_{\setminus i}, \mathbf{y}_{\setminus i}(\mathbf{x}_{\setminus i} - \mathbf{x}_i)^2) \\ &= \{(y_j(x_j - \mathbf{x}_i)^2 P(x_j))_{j \neq i} : \deg P \leq k-3\} \end{aligned} $$

$$ \mathcal{C} * \mathcal{X} = \mathcal{D} $$
5. A new tool : quadratic forms
Going to the big field

$\mathcal{C} \subseteq (\mathbb{F}_q)^n$, $\mathcal{C}_{\mathbb{F}_{q^m}} \stackrel{\text{def}}{=} \text{linear span of } \mathcal{C} \text{ over } \mathbb{F}_{q^m}$.

**Proposition 1.**

$$ (\mathbf{Alt}_r(\mathbf{x}, \mathbf{y})^{\perp})_{\mathbb{F}_{q^m}} = \sum_{j=0}^{m-1} \mathbf{GRS}_r(\mathbf{x}, \mathbf{y})^{(q^j)} = \sum_{j=0}^{m-1} \mathbf{GRS}_r(\mathbf{x}^{q^j}, \mathbf{y}^{q^j}) $$

$$ c_a \stackrel{\text{def}}{=} yx^a \in (\mathbf{Alt}_r(\mathbf{x}, \mathbf{y})^{\perp})_{\mathbb{F}_{q^m}} $$

$$ c_0 * c_2 = c_1^2 $$
Quadratic relations between codewords

C an $[n, k]$-code over $\mathbb{F}$, $\mathcal{V} = \{v_1, \dots, v_k\}$ a basis of $\mathbb{F}$

$$
\mathcal{C}_{\text{rel}}(\mathcal{V}) \stackrel{\text{def}}{=} \{ \mathbf{c} = (c_{i,j})_{1 \le i \le j \le k} \mid \sum_{i \le j} c_{i,j} \mathbf{v}_i \star \mathbf{v}_j = 0 \} \subseteq \mathbb{F}^{\binom{k+1}{2}}
$$

$$
Q_c(x_1, \dots, x_k) = \sum_{i \le j} c_{i,j} x_i x_j
$$

$$
\mathbf{x} \mathbf{M}_c \mathbf{y}^\top = Q_c(\mathbf{x} + \mathbf{y}) - Q_c(\mathbf{x}) - Q_c(\mathbf{y})
$$

$$
\mathcal{C}_{\text{mat}}(\mathcal{V}) \stackrel{\text{def}}{=} \left\{ \mathbf{M}_c = (m_{i,j})_{\substack{1 \le i \le k \\ 1 \le j \le k}} \mid \mathbf{c} = (c_{i,j})_{1 \le i \le j \le k} \in \mathcal{C}_{\text{rel}}(\mathcal{V}) \right\}
$$

$$
M_c \stackrel{\text{def}}{=} \begin{cases} m_{i,j} \stackrel{\text{def}}{=} m_{j,i} \stackrel{\text{def}}{=} c_{i,j}, & 1 \le i < j \le k, \\ m_{i,i} \stackrel{\text{def}}{=} 2c_{i,i}, & 1 \le i \le k. \end{cases}
$$
Low rank matrices

$$
c_0 * c_2 = c_1^2 \Rightarrow
$$

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

basis invariant, since ∃ an invertible matrix P such that

$$
\mathcal{C}_{\text{mat}}(\mathcal{A}) = P \mathcal{C}_{\text{mat}}(\mathcal{B}) P^{\top}
$$
MinRank Problem

**Problem 1. [odd characteristic]** Let $M_1, \cdots, M_K$ be $K$ symmetric matrices in $F^{N \times N}$, find an $M \in \langle M_1, \cdots, M_K \rangle_F$ of rank 3.

**Problem 2. [characteristic 2]** Let $M_1, \cdots, M_K$ be $K$ skew-symmetric matrices in $F^{N \times N}$, find an $M \in \langle M_1, \cdots, M_K \rangle_F$ of rank 2.

► Geometric argument on matrix codes $\Rightarrow$ probability that there are rank 2 (char 2) or rank 3 matrix in a random matrix code of the same dimension(s) as $C_{\text{mat}}(\mathcal{V})$ when $\text{rate}(\mathcal{C}) \le 1/3$ is $o(1)$.
Algebraic modeling in characteristic 2

• $\mathcal{C}$ an $[n, k]$ code,

• $\mathcal{C}_{\text{mat}}(\mathcal{V}) \in \mathbb{F}^{k \times k}$ the associated skew-symmetric matrix code
$\dim \mathcal{C}_{\text{mat}}(\mathcal{V}) = \binom{k}{2} - (n-k)$ when $\mathcal{C}$ is not [FGOPT11]-
distinguishable.

• skew-symmetric $M = (m_{ij})_{\substack{1 \le i \le k \\ 1 \le j \le k}} \in \mathbb{F}^{k \times k}$

$$
\begin{align*}
\text{rank}(M) \le 2 &\Rightarrow \text{ all principal minors of } M \text{ of size } 4 \text{ are } 0 \\
&\Rightarrow m_ab m_c_d + m_a c m_b d + m_a d m_b c = 0, \forall a, b, c, d
\end{align*}
$$

$$
M \in \mathcal{C}_{\text{mat}}(\mathcal{V}) \rightarrow n-k \text{ linear equations}
$$
Hilbert Series

* Homogeneous ideal $\mathcal{I} \in \mathbb{K}[z]$, $z = (z_1, \dots, z_n)$,

* Hilbert function of the ring $R = \mathbb{K}[z]/\mathcal{I}$ defined as

$$ \mathrm{HF}_R(d) \stackrel{\mathrm{def}}{=} \dim_{\mathbb{K}}(\mathbb{K}[z]_d) - \dim_{\mathbb{K}}(\mathcal{I}_d) $$

$$ \mathbb{K}[z]_d \stackrel{\mathrm{def}}{=} \{f \in \mathbb{K}[z] \mid \mathrm{deg}(f) = d\} $$

$$ \mathcal{I}_d \stackrel{\mathrm{def}}{=} \mathcal{I} \cap \mathbb{K}[z]_d $$

Can be computed in time $\approx n^{\omega d}$
Generic linear code/Goppa or alternant code

► alternant/Goppa case: $HF(d) > 0$ for all $d$.

► generic linear $[n, k]$-code:

$$ 
\begin{aligned}
HF(d) &= \max(0, \sum_{i=0}^{d} (-1)^i \binom{s}{i} HF(d-i)) \\
&= \max(0, \sum_{i=0}^{d} (-1)^i \binom{s}{i} \left( \binom{k+d-i-2}{d-i}^2 - \binom{k+d-i-2}{d-i-1} \right))
\end{aligned}
$$

where $s \stackrel{\text{def}}{=} n-k$.

$$ d_0 \stackrel{\text{def}}{=} \min\{d : HF(d) = 0\} \sim c \frac{k^2}{n-k} $$
Generalization of the distinguisher

► HF(1) = old distinguisher : HF(1) = $\binom{k+1}{2} - \dim \mathcal{C}^2$

<table><caption>Table 1: HF(2) for random, alternant and Goppa codes with $q = 4, m = 4, r = 4$. In bold = distinguishable lengths.</caption><thead><tr><th>HF(2)</th><th>256 ≥ n ≥ 77</th><th>n = 76</th><th>n = 75</th><th>n = 74</th><th>n = 73</th></tr></thead><tbody><tr><td>Random code</td><td>0</td><td>10</td><td>71</td><td>133</td><td>196</td></tr><tr><td>Alternant code</td><td><b>20</b></td><td><b>20</b></td><td>71</td><td>133</td><td>196</td></tr><tr><td>Goppa code</td><td><b>80</b></td><td><b>80</b></td><td><b>80</b></td><td>133</td><td>196</td></tr></tbody></table>
# 6. New attack in the (old) distinguishable regime

**Assumption 1.** The parameters are in the *old distinguishable regime* and $r < q + 1$ (alternant) or $r < q - 1$ (Goppa).

► Recall that

$$ (\mathbf{Alt}_r(\mathbf{x}, \mathbf{y})^{\perp})_{\mathbb{F}_{q^m}} = \sum_{j=0}^{m-1} \mathbf{GRS}_r(\mathbf{x}, \mathbf{y})^{(q^j)} = \sum_{j=0}^{m-1} \mathbf{GRS}_r(\mathbf{x}^{q^j}, \mathbf{y}^{q^j}) $$

⇒ Basis $\mathcal{A}$ of $(\mathbf{Alt}_r(\mathbf{x}, \mathbf{y})^{\perp})_{\mathbb{F}_{q^m}}$ of the form

$$ \mathcal{A} = (\mathbf{a}_0, \dots, \mathbf{a}_{r-1}, \mathbf{a}_0^q, \dots, \mathbf{a}_{r-1}^q, \dots, \mathbf{a}_0^{q^{m-1}}, \dots, \mathbf{a}_{r-1}^{q^{m-1}}), $$

$$ \mathbf{a}_i \stackrel{\text{def}}{=} \mathbf{y}\mathbf{x}^i $$

► From [MT22] the quadratic relations are generated by

$$ \mathbf{a}_a^{q^l} \star \mathbf{a}_b^{q^l} - \mathbf{a}_c^{q^l} \star \mathbf{a}_d^{q^l} \quad \text{for } a + b = c + d. $$
The Crucial Observation

The elements $\mathbf{A}$ of $\mathcal{C}_{\text{mat}}(\mathcal{A})$ are of the form (blocks of size $r$)

$$ \mathbf{A} = \begin{bmatrix} \mathbf{A}_0 & 0 & \cdots & 0 \\ 0 & \mathbf{A}_2 & & 0 \\ \vdots & & \ddots & 0 \\ 0 & \cdots & 0 & \mathbf{A}_{m-1} \end{bmatrix}, $$

If $\text{rank}(\mathbf{A}) = rm - 1 \Rightarrow \exists j : \text{rank}(\mathbf{A}_j) = r - 1, \text{rank}(\mathbf{A}_i) = r, i \neq j$

if $\mathbf{v} \in \text{ker}(\mathbf{A}) \Rightarrow \mathbf{v} = (\mathbf{0}_r, \dots, \mathbf{0}_r, \mathbf{v}_j, \mathbf{0}_r, \dots, \mathbf{0}_r)$

$\Rightarrow$ identify the vectors generating a single GRS code $\mathbf{GRS}_r(\mathbf{x}^{q^j}, \mathbf{y}^{q^j})$
Conclusion/Open Problems

▶ Finding a distinguisher in odd characteristic

▶ Turning the distinguisher into an attack

▶ Attacking Goppa codes in the whole distinguishable regime

▶ A general methodology for studying the security of the McEliece cryptosystem