Understanding binary-Goppa decoding

Daniel J.  Bernstein

Paper 2022/473 Original: eprint.iacr.org/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: Preprint.
History: 2024-07-02: last updated; 2022-04-22: published
Short URL: https://ia.cr/2022/473
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2022/473,
      author = {Daniel J.  Bernstein},
      title = {Understanding binary-Goppa decoding},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/473},
      year = {2022},
      url = {https://eprint.iacr.org/2022/473}
}