Decoding of (Interleaved) Generalized Goppa Codes

Hedongliang Liu, Sabine Pircher, Alexander Zeh, Antonia Wachter-Zeh

Abstract

Generalized Goppa Codes (GGCs) represent a versatile extension of classical Goppa codes, which are foundational to the security of the McEliece cryptosystem. This work provides a rigorous theoretical foundation for GGCs, deriving formal parity-check matrices and establishing tighter bounds on minimum distance. Furthermore, the paper introduces explicit, quadratic-time decoding algorithms for both standard and interleaved GGC variants. Notably, the interleaved decoding approach allows for error correction beyond the standard theoretical limits, offering significant potential for optimizing post-quantum cryptographic parameters.

Introduction

Classical Goppa codes are a cornerstone of the McEliece cryptosystem, a leading candidate for post-quantum security that has resisted cryptanalysis for over four decades. However, these codes suffer from a rigid relationship between field size ($q$) and code length ($n$), often requiring large fields for longer codes, which increases computational overhead for encryption and decryption.

Generalized Goppa Codes (GGCs) address this limitation by utilizing "code locator polynomials" of arbitrary degree, rather than the degree-one locators used in classical versions. Despite their potential, GGCs previously lacked formal proofs for distance bounds and efficient decoding algorithms. This paper fills these gaps, particularly for interleaved GGCs designed to handle burst errors.

Methodology

The authors formalize GGCs through several key algebraic developments:

  • Parity-Check Matrix Derivation: Utilizing the Extended Euclidean Algorithm (EEA), the authors derive a general parity-check matrix ($H$) for GGCs with locators of any degree.
  • Syndrome-Based Decoding: A quadratic-time algorithm is proposed to solve the "Key Equation," identifying error locations and values.
  • Interleaving and Joint Decoding: To address burst errors, interleaved GGCs are defined. A joint decoding algorithm leverages shared error positions across multiple codewords to decode beyond the "half-minimum distance" limit typical of unique decoders.
  • Separable Goppa Codes: The study focuses on "separable" GGCs, where the Goppa polynomial has distinct roots, enabling a larger minimum distance bound.

Results and Analysis

The theoretical findings are validated through a comparison of code parameters for binary separable GGCs, comparing standard Goppa codes (GC) against various Generalized versions (GGC-2, GGC-3, GGC-8).

Table I: Comparison of code parameters for binary separable Goppa codes (GC) and Generalized Goppa codes (GGC) across various lengths.

Key insights from the analysis include:

  • Field Size Flexibility: GGCs allow for significantly smaller field sizes for a fixed code length. For instance, a standard Goppa code of length 8192 requires a field size of $2^{13}$, whereas a GGC with degree-8 locators can achieve the same length using a binary field ($2^2$).
  • Improved Distance Bounds: The authors prove that using locators with even degrees improves the lower bound on the minimum Hamming distance compared to the general case.
  • Decoding Beyond the Limit: By interleaving $w$ codewords, the joint decoder can correct up to $\frac{w}{w+1} \cdot d_{sep}$ errors. As $w$ increases, this capability approaches the full minimum distance ($d_{sep}$), effectively doubling the error-correction capacity of standard unique decoding.
  • Cryptographic Trade-offs: While GGCs reduce field size, maintaining security (minimum distance) requires increasing the degree of the Goppa polynomial. As shown in Table I, this can lead to an increase in the public key size ($|pk|$), representing a critical trade-off for cryptographic implementation.

Conclusion

This research provides the first formal proofs for the parity-check matrix and minimum distance bounds of GGCs, previously only conjectured. While the reduction in field size offers computational advantages, the resulting increase in public key size remains a challenge. Future research should explore key compression techniques for GGCs and provide hardware benchmarks to quantify the speedups offered by smaller field operations. Additionally, a more granular analysis of the failure rates for the probabilistic joint decoding algorithm would enhance its applicability in high-reliability systems.

Summary updated

Abstract

Generalized Goppa codes are defined by a code locator set <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$L$</tex> of polynomials and a Goppa polynomial G(x). When the degree of all code locator polynomials in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$L$</tex> 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.
BibTeX
@inproceedings{liu2021decoding,
  author = {Hedongliang Liu and Sabine Pircher and Alexander Zeh and Antonia Wachter-Zeh},
  title = {{Decoding of (Interleaved) Generalized Goppa Codes}},
  booktitle = {ISIT},
  year = {2021},
  url = {https://openreview.net/forum?id=sRwganK2eET},
}
Figure