Understanding binary-Goppa decoding

Understanding binary-Goppa decoding

2024-03-05 | Daniel J. Bernstein
This paper reviews a polynomial-time algorithm to correct $t$ errors in classical binary Goppa codes defined by squarefree degree-$t$ polynomials. The proof is broken down into simpler steps, including a proof of a simple Reed–Solomon decoder. The algorithm is simpler than Patterson’s algorithm, and all algorithm layers are expressed as Sage scripts with test scripts. The paper also covers the use of decoding within the Classic McEliece cryptosystem, including reliable recognition of valid inputs. The paper includes formalizations of theorems in HOL-Light and Lean, and discusses the benefits of simplicity in software optimization, timing attack protection, and formal verification.This paper reviews a polynomial-time algorithm to correct $t$ errors in classical binary Goppa codes defined by squarefree degree-$t$ polynomials. The proof is broken down into simpler steps, including a proof of a simple Reed–Solomon decoder. The algorithm is simpler than Patterson’s algorithm, and all algorithm layers are expressed as Sage scripts with test scripts. The paper also covers the use of decoding within the Classic McEliece cryptosystem, including reliable recognition of valid inputs. The paper includes formalizations of theorems in HOL-Light and Lean, and discusses the benefits of simplicity in software optimization, timing attack protection, and formal verification.
Reach us at info@study.space