List-decoding of binary Goppa codes up to the binary Johnson bound

Daniel Augot 1, * Morgan Barbier 1 Alain Couvreur 2
* Auteur correspondant
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Résumé : Nous étudions le décodage en liste des codes alternants, dont notamment les codes de Goppa classiques. La considération majeure est de prendre en compte la taille de l'alphabet, qui influe sur la capacité de correction, surtout dans le cas de l'alphabet binaire. Cela revient à comparer la borne de Johnson que nous appelons générique, à la borne de Johnson que nous appelons $q$-aire, qui prend en compte la taille $q$ du corps. Cette différence est d'autant plus sensible que $q$ est petit. Essentiellement, le cas le plus favorable est celui de l'alphabet binaire pour lequel on peut augmenter significativement le rayon du décodage en liste. Et ce, d'autant plus que la distance minimale relative construite du code alternant binaire est proche de $1/2$. Bien que le résultat annoncé ici, à savoir le rayon de décodage en liste des codes de Goppa binaires, soit nouveau, il peut assez facilement être déduit de sources relativement peu connues (V.~ Guruswami, R.~M.~Roth and I.~Tal, R~.M.~Roth) et dont les auteurs n'ont apparemment pas pensé à aborder les codes de Goppa binaires. Seul D.~J.~Bernstein a traité le décodage en liste des codes de Goppa dans une prépublication. Les références sont données dans l'introduction. Nous proposons un contenu autonome, et aussi une analyse de la complexité de l'algorithme étudié, qui est quadratique en la longueur $n$ du code, si on se tient à distance du rayon relatif de décodage maximal, et en $O(n^7)$ pour le rayon de décodage maximal.
Type de document :
Rapport
[Research Report] RR-7490, INRIA. 2010, pp.23
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00547106
Contributeur : Daniel Augot <>
Soumis le : mercredi 15 décembre 2010 - 17:15:25
Dernière modification le : jeudi 12 avril 2018 - 01:47:40
Document(s) archivé(s) le : jeudi 30 juin 2011 - 13:11:10

Fichiers

RR-7490.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00547106, version 1
  • ARXIV : 1012.3439

Collections

Citation

Daniel Augot, Morgan Barbier, Alain Couvreur. List-decoding of binary Goppa codes up to the binary Johnson bound. [Research Report] RR-7490, INRIA. 2010, pp.23. 〈inria-00547106〉

Partager

Métriques

Consultations de la notice

393

Téléchargements de fichiers

265