Paper 2010/372

Decoding square-free Goppa codes over $\F_p$

Paulo S. L. M. Barreto, Richard Lindner, and Rafael Misoczki

Abstract

We propose a new, efficient decoding algorithm for square-free (irreducible or otherwise) Goppa codes over $\F_p$ for any prime $p$. If the code in question has degree $t$ and its average code distance is at least $(4/p)t + 1$, the proposed decoder can uniquely correct up to $(2/p)t$ errors with high probability. The correction capability is higher if the distribution of error magnitudes is not uniform, approaching or reaching $t$ errors when any particular error value occurs much more often than others or exclusively. This makes the method interesting for (semantically secure) cryptosystems based on the decoding problem for permuted and punctured Goppa codes.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
coding-based cryptosystemserror correctionefficient algorithms
Contact author(s)
pbarreto @ larc usp br
History
2010-07-02: revised
2010-07-02: received
See all versions
Short URL
https://ia.cr/2010/372
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/372,
      author = {Paulo S.  L.  M.  Barreto and Richard Lindner and Rafael Misoczki},
      title = {Decoding square-free Goppa codes over $\F_p$},
      howpublished = {Cryptology ePrint Archive, Paper 2010/372},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/372}},
      url = {https://eprint.iacr.org/2010/372}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.