On decoding algorithms for algebraic geometry codes beyond half the minimum distance
Sur des algorithmes de décodage de codes géométriques au delà de la moitié de la distance minimale
Résumé
This thesis deals with algebraic geometric (AG) codes and theirdecoding. Those codes are composed of vectors constructed by evaluatingspecific functions at points of an algebraic curve. The underlyingalgebraic structure of these codes made it possible to design severaldecoding algorithms. A first one, for codes from plane curves isproposed in 1989 by Justesen, Larsen, Jensen, Havemose and Hoholdt. Itis then extended to any curve by Skorobatov and Vladut and called"basic algorithm" in the literature. A few years later, Pellikaan andindependently Koetter, give a formulation without algebraic geometryusing simply the language of codes. This new interpretation, takes thename "Error Correcting Pairs" (ECP) algorithm and represents abreakthrough in coding theory since it applies to every code having acertain structure which is described only in terms of component-wiseproducts of codes. The decoding radius of this algorithm depends onthe code to which it is applied. For Reed-Solomon codes, it reacheshalf the minimum distance, which is the threshold for the solution tobe unique. For AG, the algorithm almost always manages todecode a quantity of errors equal to half the designeddistance. However, the success of the algorithm is only guaranteed fora quantity of errors less than half the designed distance minussome multiple curve's genus. Several attempts were thenmade to erase this genus-proportional penalty. A first decisiveresult was that of Pellikaan, who proved the existence of an algorithmwith a decoding radius equal to half the designed distance. Thenin 1993 Ehrhard obtained an effective procedure for constructing such analgorithm.In addition to the algorithms for unique decoding, AG codes havealgorithms correcting amount of errors greater than half thedesigned distance. Beyond this quantity, the uniqueness of thesolution may not be guaranteed. We then use a so-called "listdecoding" algorithm which returns the list of any possiblesolutions. This is the case of Sudan's algorithm for Reed-Solomoncodes. Another approach consists in designing algorithms, whichreturns a single solution but may fail. This is the case ofthe "power decoding". Sudan's and power decoding algorithms have firstbeen designed for Reed-Solomon codes, then extended to AG codes. Weobserve that these extensions do not have the same decoding radii:that of Sudan algorithm is lower than that of the power decoding,the difference being proportional to the genus of the curve.In this thesis we present two main results. First, we propose a newalgorithm that we call "power error locating pairs" which, like theECP algorithm, can be applied to any code with a certain structuredescribed in terms of component-wise products. Compared to the ECPalgorithm, this algorithm can correct errors beyond half thedesigned distance of the code. Applied to Reed-Solomon or to AG codes,it is equivalent to the power decoding algorithm. But it can also beapplied to specific cyclic codes for which it can be used to decodebeyond half the Roos bound. Moreover, this algorithm applied to AGcodes disregards the underlying geometric structure whichopens up interesting applications in cryptanalysis.The second result aims to erase the penalty proportional to thegenus in the decoding radius of Sudan's algorithm forAG codes. First, by following Pellikaan's method, weprove that such an algorithm exists. Then, by combining andgeneralizing the works of Ehrhard and Sudan, we give aneffective procedure to build this algorithm.
Cette thèse porte sur les codes géométriques et leur décodage. Cescodes sont constitués de vecteurs d'evaluations de fonctionsspécifiques en des points d'une courbe algébrique. La structurealgébrique sous-jacente de ces codes a permis de concevoir plusieursalgorithmes de décodage. Un premier algorithme pour les codesprovenant de courbes planes est proposé en 1989 par Justesen, Larsen,Jensen, Havemose et Hoholdt. Il est ensuite étendu à toute courbe parSkorobatov et Vladut et appelé "basic algorithm" dans laliterature. Quelques années plus tard, Pellikaan et indépendammentKoetter en donnent une formulation sans géométrie algébrique utilisantsimplement le langage des codes. Cette nouvelle interprétation prendle nom d'algorithme "Error Correcting Pairs" (ECP) et représente unepercée en théorie des codes, car l'algorithme s'applique à toutcode muni d'une certaine structure qui se décrit uniquement entermes de produits coordonnées par coordonnées de codes. Le rayon dedécodage de cet algorithme dépend du code auquel il est appliqué. Pourles codes de Reed-Solomon, il atteint la moitié de la distanceminimale,seuil d'unicité de la solution. Pour les codes géométriques,l'algorithme arrive à décoder presque toujours une quantité d'erreurségale à la moitié de la distance construite. Toutefois, le bonfonctionnement de l'algorithme n'est garanti que pour une quantitéd'erreurs inférieure à la moitié de la distance construite moins unmultiple du genre de la courbe. Plusieurs tentatives ont ensuite été menéespour effacer cette penalité dûe au genre. Un premierrésultat déterminant a été celui de Pellikaan, qui a prouvél'existence d'un algorithme avec rayon de décodage égal à la moitié dela distance construite. Puis,en 1993 Ehrhard est parvenu à uneprocédure effective pour construire un tel algorithme.En plus des algorithmes pour le décodage unique,les codesgéométriques disposent d'algorithmes corrigeant une quantité d'erreurssupérieure à la moitié de la distance construite. Au delà de cettequantité, l'unicité de la solution pourrait ne pas être assurée. Onutilise alors des algorithmes dits de "decodage en liste" quirenvoient la liste des solutions possibles. C'est le cas del'algorithme de Sudan. Une autre approche consiste à concevoirdes algorithmes qui renvoient une unique solution mais peuvent échouer.C'est le cas du "power decoding". Les algorithmes de Sudan etdu power decoding ont d'abord été conçus pour les codes deReed-Solomon,puis étendus aux codes géométriques.On observe que ces extensions n'ont pas les mêmes rayonsde décodage: celui de l'algorithme de Sudan est inférieur à celui duPower decoding, la différence étant proportionnelle au genre de la courbe.Dans cette thèse nous présentons deux résultatsprincipaux. Premièrement, nous proposons un nouvel algorithme que nousappelons "power error locating pairs" qui, comme l'algorithme ECP,peut être appliqué à tout code muni d'une certainestructure se décrivant en termes de produits coordonnées parcoordonnées. Comparé à l'algorithme ECP, cetalgorithme peut corriger des erreurs au delà de la moitié de ladistance construite du code. Appliqué aux codes de Reed--Solomon ou,plus généralement, aux codes géométriques, il est equivalent àl'algorithme du power decoding. Mais il peut aussi être appliqué àdes codes cycliques spécifiques pour lesquels il permet de décoder audelà de la moitié de la borne de Roos. Par ailleurs, cet algorithmeappliqué aux codes géométriques fait abstraction de la structuregéométrique sous-jascente ce qui ouvre d'intéressantes applications encryptanalyse.Le second résultat a pour but d'effacer la penalité proportionnelle augenre dans le rayon de décodage de l'algorithme de Sudan pour lescodes géométriques. D'abord, en suivant la méthode de Pellikaan, nousprouvons que un tel algorithme existe. Puis, engénéralisant les travaux de Ehrhard et Sudan, nous donnons uneprocédure effective pour construire cet algorithme.
| Origine | Version validée par le jury (STAR) |
|---|