Paper 2022/473
Understanding binary-Goppa decoding
Daniel J. Bernstein
Abstract
This paper reviews, from bottom to top, a polynomial-time algorithm to correct t errors in classical binary Goppa codes defined by squarefree degree-t polynomials. The proof is factored through a proof of a simple Reed--Solomon decoder, and the algorithm is simpler than Patterson's algorithm. All algorithm layers are expressed as Sage scripts. The paper also covers the use of decoding inside the Classic McEliece cryptosystem, including reliable recognition of valid inputs.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint. Minor revision.
- Contact author(s)
- authorcontact-goppadecoding @ box cr yp to
- History
- 2022-04-22: received
- Short URL
- https://ia.cr/2022/473
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/473, author = {Daniel J. Bernstein}, title = {Understanding binary-Goppa decoding}, howpublished = {Cryptology ePrint Archive, Paper 2022/473}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/473}}, url = {https://eprint.iacr.org/2022/473} }