Skip to Main content Skip to Navigation
Reports

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

Daniel Augot 1, * Morgan Barbier 1 Alain Couvreur 2
* Corresponding author
1 TANC - Algorithmic number theory for cryptology
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : We study the list-decoding problem of alternant codes, with the notable case of classical Goppa codes. The major consideration here is to take into account the size of the alphabet, which shows great influence on the list-decoding radius. This amounts to compare the \emph{generic} Johnson bound to the \emph{$q$-ary} Johnson bound. This difference is important when $q$ is very small. Essentially, the most favourable case is $q=2$, for which the decoding radius is greatly improved, notably when the relative minimum distance gets close to $1/2$. Even though the announced result, which is the list-decoding radius of binary Goppa codes, is new, it can be rather easily made up from previous sources (V.~ Guruswami, R.~M.~Roth and I.~Tal, R~.M.~Roth), which may be a little bit unknown, and in which the case of binary Goppa codes has apparently not been thought at. Only D.~J.~Bernstein treats the case of binary Goppa codes in a preprint. References are given in the introduction. We propose an autonomous treatment and also a complexity analysis of the studied algorithm, which is quadratic in the blocklength $n$, when decoding at some distance of the relative maximum decoding radius, and in $O(n^7)$ when reaching the maximum radius.
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/inria-00547106
Contributor : Daniel Augot <>
Submitted on : Wednesday, December 15, 2010 - 5:15:25 PM
Last modification on : Thursday, March 5, 2020 - 6:25:19 PM
Long-term archiving on: : Thursday, June 30, 2011 - 1:11:10 PM

Files

RR-7490.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

534

Files downloads

583