| Paper ID | D2-S3-T2.3 |
| Paper Title |
Decoding of (Interleaved) Generalized Goppa Codes |
| Authors |
Hedongliang Liu, Technical University of Munich, Germany; Sabine Pircher, Technical University of Munich; HENSOLDT Cyber GmbH, Germany; Alexander Zeh, HENSOLDT Cyber GmbH, Germany; Antonia Wachter-Zeh, Technical University of Munich, Germany |
| Session |
D2-S3-T2: Decoding of Algebraic Codes |
| Chaired Session: |
Tuesday, 13 July, 22:40 - 23:00 |
| Engagement Session: |
Tuesday, 13 July, 23:00 - 23:20 |
| Abstract |
Generalized Goppa codes are defined by a \emph{code locator} set $\cL$ of polynomials and a \emph{Goppa polynomial} $G(x)$. When the degree of all code locator polynomials in $\cL$ is one, generalized Goppa codes are classical Goppa codes. In this work, \emph{binary generalized Goppa codes} are investigated. First, a parity-check matrix for these codes with code locators of any degree is derived. A careful selection of the code locators leads to a lower bound on the minimum Hamming distance of generalized Goppa codes which improves upon previously known bounds. A quadratic-time decoding algorithm is presented which can decode errors up to half of the minimum distance. \emph{Interleaved generalized Goppa codes} are introduced and a joint decoding algorithm is presented which can decode errors beyond half the minimum distance with high probability. Finally, some code parameters and how they apply to the \textit{Classic McEliece} post-quantum cryptosystem are shown.
|
