# Les codes Low Rank Parity Check (LRPC)

Abdul Karim Yazbek, Jean-Pierre Cances, Vahid Meghdadi

► To cite this version:

Abdul Karim Yazbek, Jean-Pierre Cances, Vahid Meghdadi. Les codes Low Rank Parity Check (LRPC). 2017. hal-01571233

HAL Id: hal-01571233

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

Preprint submitted on 8 Aug 2017

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>
# Les codes Low Rank Parity Check

Yazbek Abdul Karim, Jean-Pierre Cances, Vahid Meghdadi,

Univ. Limoges, CNRS, XLIM, UMR 7252, F-87000 Limoges, Fr,
e-mail: abdel-karim.yazbeck@ensil.unilim.fr

## Résumé

Dans cet article, nous introduisons une nouvelle famille de codes à métriques de rang : Les codes LRPC. Nous développons les équations de sa construction algébrique et nous proposons un algorithme de décodage probabiliste efficace. Cette famille de codes peut être considérée comme l'équivalent des codes Low Density Parity Check (LDPC) classiques pour la métrique de rang.

## 1. LOW RANK PARITY CHECK CODES (LRPC)

L'idée de ces codes est de généraliser l'approche des codes LDPC classiques pour la distance de Hamming à la métrique de rang. Il y a une analogie entre matrices de faible densité et de matrices à faible rang.

Dans ce chapitre, le travail se base seulement sur l'article [1] de Philippe Gaborit.

**Définition 1.** Un code LRPC est un code de rang $d$, de longueur $n$ et de dimension $k$ dans $\mathbb{F}_{q^m}$, ce code a comme $H(h_{ij})$ une matrice de parité de taille $(n-k) \times n$ tels que le sous espace vectoriel de $\mathbb{F}_{q^m}$ généré par ses coefficients $h_{ij}$ est de dimension au plus $d$. Nous appelons cette dimension le poids de $H$. En notant $F$ le sous-espace vectoriel de $\mathbb{F}_{q^m}$ généré par les coefficients $h_{ij}$ de $H$, on note $\{F_1, F_2, \dots, F_d\}$ une de ses bases.

## 2. ÉCRITURE DES ÉQUATIONS DU SYNDROME DANS LE CORPS $\mathbb{F}_q$ POUR LES CODES LRPC

La structure particulière des codes LRPC permet d'exprimer formellement les équations du syndrome dans $\mathbb{F}_{q^m}$ en équations dans la base $\mathbb{F}_q$, il permet d'obtenir un algorithme de décodage très efficace, que nous allons voir dans la prochaine section. Nous décrivons dans ce qui suit la façon d'obtenir une telle transformation, en particulier, nous introduisons une matrice $A_H^r$, qui sera utiliser pour la procédure de décodage.

Supposons que l'erreur $e(e_1, \dots, e_n)$ de poids $r$ se situe dans un espace d'erreur $E$ de dimension $r$ généré par une base $\{E_1, E_2, \dots, E_r\}$, puis tout les $e_i(1 \le i \le n)$ peuvent être écrits sous la forme $e_i = \sum_{j=1}^r e_{ij}E_j$. La matrice $H = (h_{ij})$ est réalisé de telle sorte que $h_{ij}$ appartiennent à un espace $F$ de dimension $d$ généré par $\{F_1, F_2, \dots, F_d\}$, alors pour tout $1 \le i \le n-k$, $1 \le j \le n$, $h_{ij} = \sum_{l=1}^d h_{ijl}F_l$, avec $h_{ijl} \in \mathbb{F}_q$.

Supposons en outre que la dimension de l'espace $\langle F_1E_1, F_1E_2, \dots, F_rE_r, F_2E_1, \dots, F_dE_r \rangle$ est exactement $rd$, il est alors possible d'exprimer les équations de syndrome $H.e^t = s$ dans $\mathbb{F}_{q^m}$ en équations dans la base
Fq, en exprimant formellement les $e_i$ dans la base $\{E_1, E_2, \dots, E_r\}$ et les coordonnées du syndrome dans
le produit des bases $<F_1E_1, F_1E_2, \dots, F_1E_r, F_2E_1, \dots, F_dE_r>$.

Plus formellement, il existe une matrice $A_H^r$ de taille $(n-k)rd \times nr$ dans $\mathbb{F}_q$ tels que les équations du syndrome $H.e^t = s$ dans $\mathbb{F}_{q^m}$ deviennent un système d'équations $A_H^r.e^t = s'$ dans $\mathbb{F}_q$, où $s'$ correspond à un vecteur $(n-k)rd$ dans $\mathbb{F}_q$ correspondant aux coordonnées du syndrome $s$, $(s_1, \dots, s_n-k)$, où chaque $s_i$ est écrit dans la base $<F_1E_1, F_1E_2, \dots, F_1E_r, F_2E_1, \dots, F_dE_r>$ du produit de deux espaces $<E.F>$, et où $e'$ est un vecteur $nr$ sur $\mathbb{F}_q$ correspondant aux coordonnées d'erreur $(e_1, \dots, e_n)$, où chaque $e_i$ est écrit dans la base $\{E_1, E_2, \dots, E_r\}$. Si l'on procède de cette façon la matrice $A_H^r$ de taille $nr \times (n-k)rd$ ne dépend que des coordonnées $h_{ij}$ écrit dans la base $\{F_1, F_2, \dots, F_d\}$, et donc $A_H^r$ ne dépend pas de l'erreur $e$, mais de façon unique de son dimension $r$. Pour des différents erreurs $e$, on a juste à écrire $s$ comme $s'$ dans le produit de deux espaces $<E.F>$ puis résoudre le système $A_H^r.e^t = s'$.

$$
H.e = \begin{pmatrix} h_{1,1} & h_{1,2} & \cdots & h_{1,n} \\ h_{2,1} & h_{2,2} & \cdots & h_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ h_{n-k,1} & h_{n-k,2} & \cdots & h_{n-k,n} \end{pmatrix} \times \begin{pmatrix} e_1 \\ e_2 \\ \vdots \\ e_n \end{pmatrix} = \begin{pmatrix} s_1 \\ s_2 \\ \vdots \\ s_{n-k} \end{pmatrix}
$$

Alors,

$$
\left\{
\begin{array}{lclcl}
h_{1,1}e_1 & + & h_{1,2}e_2 & + & \dots & + & h_{1,n}e_n = s_1 \\
h_{2,1}e_1 & + & h_{2,2}e_2 & + & \dots & + & h_{2,n}e_n = s_1 \\
\vdots &  & \vdots &  & \ddots &  & \vdots \\
h_{n-k,1}e_1 & + & h_{n-k,2}e_2 & + & \dots & + & h_{n-k,n}e_n = s_1
\end{array}
\right.
$$

Or,

$$
h_{ij}.e_j = \begin{pmatrix} h_{ij1} \\ h_{ij2} \\ \vdots \\ h_{ijd} \end{pmatrix} \cdot \begin{pmatrix} e_{j1} & e_{j2} & \cdots & e_{jr} \end{pmatrix} = \begin{pmatrix} h_{ij1}e_{j1} & h_{ij1}e_{j2} & \cdots & h_{ij1}e_{jr} \\ h_{ij2}e_{j1} & h_{ij2}e_{j2} & \cdots & h_{ij2}e_{jr} \\ \vdots & \vdots & \ddots & \vdots \\ h_{ijd}e_{j1} & h_{ijd}e_{j2} & \cdots & h_{ijd}e_{jr} \end{pmatrix}
$$

Et,

$$
s_i = \begin{pmatrix} s_{i11} & s_{i12} & \cdots & s_{i1r} \\ s_{i21} & s_{i22} & \cdots & s_{i2r} \\ \vdots & \vdots & \ddots & \vdots \\ s_{id1} & s_{id2} & \cdots & s_{idr} \end{pmatrix}
$$
Si on remplace dans chaque équation on obtient,

$$
\begin{pmatrix}
\sum_{j=1}^{n} h_{1j1} e_{j1} & \sum_{j=1}^{n} h_{1j1} e_{j2} & \cdots & \sum_{j=1}^{n} h_{1j1} e_{jr} \\
\vdots & \vdots & \ddots & \vdots \\
\sum_{j=1}^{n} h_{1jd} e_{j1} & \sum_{j=1}^{n} h_{1jd} e_{j2} & \cdots & \sum_{j=1}^{n} h_{1jd} e_{jr} \\
\vdots & \vdots & \ddots & \vdots \\
\sum_{j=1}^{n} h_{(n-k)j1} e_{j1} & \sum_{j=1}^{n} h_{(n-k)j1} e_{j2} & \cdots & \sum_{j=1}^{n} h_{(n-k)j1} e_{jr} \\
\vdots & \vdots & \ddots & \vdots \\
\sum_{j=1}^{n} h_{(n-k)jd} e_{j1} & \sum_{j=1}^{n} h_{(n-k)jd} e_{j2} & \cdots & \sum_{j=1}^{n} h_{(n-k)jd} e_{jr}
\end{pmatrix}
=
\begin{pmatrix}
s_{111} & s_{112} & \cdots & s_{11r} \\
\vdots & \vdots & \ddots & \vdots \\
s_{1d1} & s_{1d2} & \cdots & s_{1dr} \\
\vdots & \vdots & \ddots & \vdots \\
s_{(n-k)11} & s_{(n-k)12} & \cdots & s_{(n-k)1r} \\
\vdots & \vdots & \ddots & \vdots \\
s_{(n-k)d1} & s_{(n-k)d2} & \cdots & s_{(n-k)dr}
\end{pmatrix}
$$

En transformant l'équation matricielle à un système on trouve,

$$
\left\{
\begin{array}{l}
\sum_{j=1}^{n} h_{1j1} e_{j1} = s_{111} \\
\vdots \\
\sum_{j=1}^{n} h_{1j1} e_{jr} = s_{11r} \\
\vdots \\
\sum_{j=1}^{n} h_{1jd} e_{j1} = s_{1d1} \\
\vdots \\
\sum_{j=1}^{n} h_{1jd} e_{jr} = s_{1dr} \\
\vdots \\
\sum_{j=1}^{n} h_{(n-k)j1} e_{j1} = s_{(n-k)11} \\
\vdots \\
\sum_{j=1}^{n} h_{(n-k)j1} e_{jr} = s_{(n-k)1r} \\
\vdots \\
\sum_{j=1}^{n} h_{(n-k)jd} e_{j1} = s_{(n-k)d1} \\
\vdots \\
\sum_{j=1}^{n} h_{(n-k)jd} e_{jr} = s_{(n-k)dr}
\end{array}
\right.
$$

Ce qui donne,
**Notation.** On note par $A_H$ la $nr \times nr$ sous-matrice inversible de $A_H^r$, on note $D_H = A_H^{-1}$ une matrice de décodage de $H$.

La matrice $D_H$ permet de récupérer directement les valeurs de $e_{ij}$

### 3. L'ALGORITHME DE DÉCODAGE DE CODE LRPC

#### A. L'idée générale

L'idée générale de l'algorithmme est d'utiliser le fait que le poids de matrice de parité est petit et que l'espace généré par les cordonnés de syndrome $\langle s_1, ..., s_{n_k} \rangle$ permet de récupérer tout l'espace produit $P = \langle F.E \rangle$ entre le support de l'erreur et la base de $H$. En connaissant l'espace $P$ et $F$ permet de récupérer $E$, après il sera facile de retrouver l'erreur $e$ en résolvant un système linéaire. Cette méthode est similaire à la procédure de décodage des codes BCH.

#### B. L'algorithmme générale de décodage

Considérons un $[n, k]$ LRPC code $C$ de petit poids $d$ sur $\mathbb{F}_{q^m}$, avec matrice génératrice $G$ et $(n-k) \times n$ matrice $H$ tel que les $h_{ij}$ sont engendrés par $\{F_1, F_2, ..., F_d\}$ et que $H$ est choisis telle que $D_H$ existe.

Supposons qu'on a reçu $y = xG + e$ pour $x$ dans $\mathbb{F}_{q^m}^k$ et $e$ dans $\mathbb{F}_{q^m}^n$ de rang $r$ tel que $\{E_1, E_2, ..., E_r\}$ est une base de $\langle e_1, ..., e_n \rangle$.

Nous considérons l'algorithmme générale de décodage suivant, cette algorithmme a une probabilité d'échec que nous allons présenter dans la prochaine section, on va donner quelque paramètre pour lequel l'algorithmme marche.

<table><caption>**Algorithmme 1 :** l'algorithmme générale de décodage pour</caption><tr><td>1.</td><td><b>Comptage d'espace syndrome</b></td><td>On commence par calculer le syndrome, après on calcule l'espace syndrome &lt; s<sub>1</sub>, ..., s<sub>n-k</sub> &gt;.</td></tr><tr><td>2.</td><td><b>Trouver le support E de l'erreur</b></td><td>On définit S<sub>i</sub> = F<sub>i</sub><sup>-1</sup>S et on calcule le support d'erreur E = S<sub>1</sub> &cap; S<sub>2</sub> &cap; ... &cap; S<sub>d</sub>.</td></tr><tr><td>3.</td><td><b>Trouver l'erreur e</b></td><td>On écrit e<sub>i</sub>(1 &le; i &le; n) dans la base {E<sub>1</sub>, E<sub>2</sub>, ..., E<sub>r</sub>} tel e<sub>i</sub> = &Sigma;<sup>r</sup><sub>j=1</sub> e<sub>ij</sub>E<sub>j</sub>.<br/>e' = (e<sub>11</sub>, e<sub>12</sub>, ..., e<sub>nr</sub>).<br/>On écrit s<sub>i</sub> dans la base P = &lt; E.F &gt;.<br/>On essaye de récupérer e' à partir du système A<sub>H</sub><sup>r</sup>.e' = s'.</td></tr><tr><td>4.</td><td><b>Trouver le message x</b></td><td>Trouver x depuis le system x.G = y - e.</td></tr></table>

#### C. L'exactitude de l'algorithmme

Nous allons prouver l'exactitude de l'algorithmme dans le cas idéal quand $dim(\langle E.F \rangle) = rd$, $dim(S) = rd$ et $dim(S_1 \cap S_2 \cap ... \cap S_d) = r$, nous allons voir dans la prochaine section que c'est le cas générale.
**Étape 1** : La première étape de l’algorithme est évidente.

**Étape 2** : Nous allons prouver que $E \subset S_1 \cap S_2 \cap \dots \cap S_d$. Puisque $S$ est le produit des deux espaces $E$ et $F$, on a $F_i \cdot E_j \in S$, pour $1 \le j \le r$, donc $E_j \in S_i$ et $E \subset S_i$, d'où $E \subset S_1 \cap S_2 \cap \dots \cap S_d$. Par hypothèse $dim(S_1 \cap S_2 \cap \dots \cap S_d) = dim(E)$ ce qui implique l'égalité de $E$ et $S_1 \cap S_2 \cap \dots \cap S_d$.

**Étape 3** : Après avoir trouver $E$, on écrit $e_i$ dans la base de $E$, dans cas on a $nr$ inconnus et $(n-k)m$ équations donc il faut que $r$ soit plus petit que $\frac{(n-k)m}{n}$.

### D. La probabilité d'échec

Nous considérons les trois différents probabilité d'échec, le cas où $dim(< E \cdot F >) = rd$ est vérifié avec une probabilité supérieure à $r \frac{q^{rd}}{q^m}$, le cas où $E = S_1 \cap S_2 \cap \dots \cap S_d$ est vérifié avec une probabilité supérieure à $r \frac{q^{rd(d+1)/2}}{q^m}$ et le cas où $dim(S) = rd$ est vérifié avec une probabilité inférieure à $q^{(n-k)-rd-1}$.

### E. La complexité de décodage

L'étape 2) et l'étape 3) sont les plus coûteux dans l'algorithme 1. Pour l'étape 2) la complexité de l'intersection des espaces vectoriels est $4r^2d^2m$ opérations dans le corps de base. Dans l'étape 3) la complexité est $n^2r^2$ pour trouver $e_{ij}$ en utilisant la matrice $D_H$.

Remarquons que $D_H$ peut être calculer et stocker dans la mémoire du codeur.

Si on résume les différents sections on obtient le théorème suivant

**Théorème 1.** Soit $H$ une matrice duale de taille $(n-k) \times n$ d'un code LRPC de petit rang $d \ge 2$ sur $\mathbb{F}_{q^m}$, l'algorithme 1 décode une erreur aléatoire $e$ de poids $r$ tel que $rd \le n-k$, avec une probabilité de succès égale à $1 - q^{-(n-k-rd)}$ et une complexité $r^2(4d^2m + n^2)$.

## RÉFÉRENCES

[1] P. Gaborit, O. Ruatta, G. Murat et G. Zémor. *Low Rank Parity Check Codes and their application in cryptography*. WCC 2013, 167-179