List-Decoding of Binary Goppa Codes up to the Binary Johnson Bound

Daniel Augot 1, 2 Morgan Barbier 1 Alain Couvreur 1, 3
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
Abstract : We study the list-decoding problem of alternant codes (which includes obviously that of classical Goppa codes). The major consideration here is to take into account the (small) size of the alphabet. This amounts to comparing the generic Johnson bound to the q-ary Johnson bound. The most favourable case is q = 2, for which the decoding radius is greatly improved. Even though the announced result, which is the list-decoding radius of binary Goppa codes, is new, we acknowledge that it can be made up from separate previous sources, which may be a little bit unknown, and where the binary Goppa codes has apparently not been thought at. Only D. J. Bernstein has treated the case of binary Goppa codes in a preprint. References are given in the introduction. We propose an autonomous and simplified treatment and also a complexity analysis of the studied algorithm, which is quadratic in the blocklength n, when decoding away of the relative maximum decoding radius.
Type de document :
Communication dans un congrès
Shokrollahi. Amin and da Rocha Jr., Valdemar C. and Costa, Sueli I. R. IEEE Information Theory Workshop, Oct 2011, Paraty, Brazil. IEEE, pp.229 - 233, 2011, 〈10.1109/ITW.2011.6089384〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00643794
Contributeur : Daniel Augot <>
Soumis le : mardi 22 novembre 2011 - 18:06:00
Dernière modification le : jeudi 10 mai 2018 - 02:06:26
Document(s) archivé(s) le : jeudi 23 février 2012 - 02:35:31

Fichier

augot_barbier_couvreur_itw.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Daniel Augot, Morgan Barbier, Alain Couvreur. List-Decoding of Binary Goppa Codes up to the Binary Johnson Bound. Shokrollahi. Amin and da Rocha Jr., Valdemar C. and Costa, Sueli I. R. IEEE Information Theory Workshop, Oct 2011, Paraty, Brazil. IEEE, pp.229 - 233, 2011, 〈10.1109/ITW.2011.6089384〉. 〈hal-00643794〉

Partager

Métriques

Consultations de la notice

469

Téléchargements de fichiers

169