TY - GEN
T1 - Decoding of (Interleaved) Generalized Goppa Codes
AU - Liu, Hedongliang
AU - Pircher, Sabine
AU - Zeh, Alexander
AU - Wachter-Zeh, Antonia
N1 - Publisher Copyright:
© 2021 IEEE.
PY - 2021/7/12
Y1 - 2021/7/12
N2 - Generalized Goppa codes are defined by a code locator set L of polynomials and a Goppa polynomial G(x). When the degree of all code locator polynomials in L is one, generalized Goppa codes are classical Goppa codes. In this work, 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. 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 Classic McEliece post-quantum cryptosystem are shown.
AB - Generalized Goppa codes are defined by a code locator set L of polynomials and a Goppa polynomial G(x). When the degree of all code locator polynomials in L is one, generalized Goppa codes are classical Goppa codes. In this work, 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. 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 Classic McEliece post-quantum cryptosystem are shown.
UR - http://www.scopus.com/inward/record.url?scp=85115057524&partnerID=8YFLogxK
U2 - 10.1109/ISIT45174.2021.9517785
DO - 10.1109/ISIT45174.2021.9517785
M3 - Conference contribution
AN - SCOPUS:85115057524
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 664
EP - 669
BT - 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2021 IEEE International Symposium on Information Theory, ISIT 2021
Y2 - 12 July 2021 through 20 July 2021
ER -