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 backed by test scripts. All theorems are formally verified. 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
Published elsewhere. IACR Communications in Cryptology
DOI
10.62056/angy4fe-3
Contact author(s)
authorcontact-goppadecoding @ box cr yp to
History
2024-07-02: last of 4 revisions
2022-04-22: received
See all versions
Short URL
https://ia.cr/2022/473
License
Creative Commons Attribution
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},
      doi = {10.62056/angy4fe-3},
      url = {https://eprint.iacr.org/2022/473}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.