Power error locating pairs

Abstract

We present a new decoding algorithm based on error locating pairs and correcting an amount of errors exceeding half the minimum distance. When applied to Reed–Solomon or algebraic geometry codes, the algorithm is a reformulation of the so-called power decoding algorithm. Asymptotically, it corrects errors up to Sudan’s radius. In addition, this new framework applies to any code benefiting from an error locating pair. Similarly to Pellikaan’s and Kötter’s approach for unique algebraic decoding, our algorithm provides a unified point of view for decoding codes with an algebraic structure beyond the half minimum distance. It permits to get an abstract description of decoding using only codes and linear algebra and without involving the arithmetic of polynomial and rational function algebras used for the definition of the codes themselves. Such algorithms can be valuable for instance for cryptanalysis to construct a decoding algorithm of a code without having access to the hidden algebraic structure of the code.

A Power decoding for algebraic geometry codes

We show how the power decoding algorithm adapts to arbitrary algebraic geometry codes. Let $C=C_L(\mathcal {X}, \mathcal {P}, G)$ and $\mathbf{y} =\mathbf{c} +\mathbf{e} \in \mathbb {F}_q^n$ the word we want to correct, where $\mathbf{c} \in C$. We have then

$$\begin{aligned} c={{\,\mathrm{ev}\,}}_{\mathcal {P}}(f)\text { with }f\in L(G). \end{aligned}$$

Furthermore, as in the previous sections, we suppose that ${{\,\mathrm{w}\,}}(\mathbf{e} )=t$ and denote the support of $\mathbf{e}$ by ${I_{{\textit{\textbf{e}}}}}$. We keep the same idea we used in the version of the algorithm for Reed–Solomon codes. Indeed, let us suppose to have $\Lambda \in \mathbb {F}_q(\mathcal {X})$ such that $\Lambda (P_i)=0$ for all $i\in {I_{{\textit{\textbf{e}}}}}$. Then, given $\ell \in \mathbb {N}$ we get

$$\begin{aligned} \Lambda (P_i)y_i^j=\Lambda (P_i)f^j(P_i)\ \ \ \ \forall \ i=1,\dots , n,\ \ j=1,\dots \ell . \end{aligned}$$

(46)

We would like then to find $\Lambda$ as above. It is easy to see that such a $\Lambda$ has to be searched in L(F) for a certain F such that $\deg (F)\hbox {\,\char 062\,}t+g$. (we will give a better bound for that soon). It is possible to see $(\Lambda , f)$ as a solution of

$$\begin{aligned} \lambda (P_i)y_i^j=\lambda (P_i)\phi ^j(P_i)\ \ \ \ \forall \ i=1,\dots , n,\ \ j=1,\dots \ell , \end{aligned}$$

(47)

that is, a system of $n\ell$ equations whose unknowns are the coordinates of $\lambda$ and $\phi$ in the basis of respectively L(F) and L(G). System (47) is not linear in the unknowns though, hence we linearise it by considering a new function $\nu _j:=\lambda \phi ^j$ for any equation. For all $j\in \{1, \dots , \ell \}$, we get

$$\begin{aligned} \nu _j\in L(F)L(jG)\subseteq L(F+jG). \end{aligned}$$

In order to use Theorem 2.9, let us fix $\deg (F)= t+2g$ and suppose $\deg (G)\hbox {\,\char 062\,}2g+1$. We get then the following problem.

Key Problem 3

Given $\mathbf{y} \in \mathbb {F}_q^n$ and $t\in \mathbb {N}$, look for $\lambda ,\nu _1, \dots , \nu _{\ell }\in \mathbb {F}_q^n(\mathcal {X})$ such that

• $\lambda \in L(F)$ with $\deg (F)= t+2g$;

• $\nu _j\in L(F+jG)$ for all $j=1,\dots ,\ell$;

• $\lambda (x_i)y_i=\nu _j(x_i)$ for all $i=1,\dots , n$ and $j=1,\dots , \ell$.

Therefore, even this case, the power decoding algorithm consists in solving a linear system and we will just consider a nonzero solution. Decoding Radius. As in the case of Reed–Solomon codes, we would like to have a solution space of dimension one. A necessary condition for that, is

$$\begin{aligned} \# unknowns\hbox {\,\char 054\,}\# equations+1. \end{aligned}$$

(48)

The number of equations is $n\ell$. For the number of unknowns, we need to know the dimension of the spaces $L(F+jG)$ for all $j=1,\dots , \ell$. The bounds we have set in the hypothesis give

$$\begin{aligned}\nonumber \dim (L(F+jG))=t+g+j\deg (G)+1. \end{aligned}$$

Hence by condition (48) we get the following decoding radius

$$\begin{aligned} t\hbox {\,\char 054\,}\frac{2n\ell -\ell (\ell +1)\deg (G)}{2(\ell +1)}-g -\frac{\ell }{\ell +1}\cdot \end{aligned}$$

(49)

Remark A.1

This bound is not a sufficient condition to have a solution, but it is not even a necessary condition. In fact, as for the power decoding algorithm for Reed–Solomon codes, we could find a good solution even for a larger value of t and on the other hand the algorithm could fail even if t fulfills condition (49).