International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Decoding square-free Goppa codes over $\F_p$

Paulo S. L. M. Barreto
Richard Lindner
Rafael Misoczki
Search ePrint
Search Google
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.
  title={Decoding square-free Goppa codes over $\F_p$},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / coding-based cryptosystems, error correction, efficient algorithms},
  note={ 14792 received 28 Jun 2010, last revised 2 Jul 2010},
  author={Paulo S. L. M. Barreto and Richard Lindner and Rafael Misoczki},