Goppa code

Goppa code[1–3]

Alternative names: LG code.

Description

A linear \(q\)-ary code defined from a polynomial \(G(x)\) over an extension field and a set of evaluation points \(L\) avoiding the roots of \(G\). Goppa codes form a central family of alternant codes, admit efficient algebraic decoding algorithms, and include the binary Goppa codes used in the McEliece cryptosystem. They can also be viewed as residue AG codes on the projective line.

Let \(G(x)\in \mathbb{F}_{q^m}[x]\) be a polynomial of degree \(r\), and let \(L=\{\alpha_1,\ldots,\alpha_n\}\subseteq \mathbb{F}_{q^m}\) be a set of distinct elements such that \(G(\alpha_i)\neq 0\) for all \(i\). The Goppa code \(\Gamma(L,G)\) is the \([n,k,d]_q\) linear code consisting of all vectors \(a=(a_1,\ldots,a_n)\in\mathbb{F}_q^n\) such that \begin{align} \sum_{i=1}^n \frac{a_i}{x-\alpha_i} \equiv 0 \pmod{G(x)}~. \tag*{(1)}\end{align}

Goppa codes are residue AG codes [4; Thm. 15.3.28]. Their duals are evaluation codes that are sometimes called geometric RS codes [5; Thm. 2.71].

Protection

The length is \(n=|L|\), the dimension satisfies \(k \geq n-mr\) where \(r=\deg G(x)\), and the minimum distance satisfies \(d \geq r+1\).

Decoding

Algebraic decoding algorithms [6]. If \( \text{deg} G(x) = 2t \) , then there exists a \(t\)-correcting algebraic decoding algorithm for \( \Gamma(L,G) \).Sugiyama et al. modification of the extended Euclidean algorithm [7,8].Binary Goppa codes can be decoded using an RS-based decoder [9].List decoder for binary Goppa codes [10].

Realizations

The McEliece public-key cryptosystem [11,12]. The protocol relies on the assumptions that Goppa-code generator matrices are hard to distinguish from random linear codes. However, there is an algorithm distinguishing between the two code classes in a time subexponential in \(n\) [13].

Notes

GAP function GoppaCode(G,L) takes in a polynomial \(G\) that satisfies the necessary conditions for a Goppa code and a list \(L\) that contains elements in \(\mathbb{F}_q\) that are not roots of \(G\). It returns a Goppa code.

Cousins

Generalized RS (GRS) code— Goppa codes are \(\mathbb{F}_q\)-subfield subcode of the dual of the GRS code over \(\mathbb{F}_{q^m}\) with evaluation points \(\alpha_i\) and factors \(v_i=G(\alpha_i)^{-1}\) ([14], pg. 523; [5]).
\(q\)-ary linear LTC— Goppa codes are locally testable [15].
Chien-Choy generalized BCH (GBCH) code— In the binary case, GBCH\((z^{n-1},G)\) is the Goppa code \(\Gamma(L,G)\) where \(L\) consists of the \(n\)th roots of unity [16; pg. 360].
Quantum Goppa code— Classical Goppa codes over various algebraic curves are used to construct quantum Goppa codes.

Member of code lists

Primary Hierarchy

Classical Domain

Galois-field Kingdom

\(q\)-ary codeECC

Additive \(q\)-ary codeECC

Linear \(q\)-ary codeECC

Evaluation code

Evaluation AG codeAG ECC

Residue AG codeAG ECC

Parents

Residue AG code

Cartier codeLinear \(q\)-ary AG ECC

Goppa codes are Cartier codes from a curve of genus zero [17].

Alternant codeLinear \(q\)-ary ECC

Goppa codes are a special case of alternant codes [16; Ch. 12].

Goppa code

Children

Primitive narrow-sense BCH code

Primitive narrow-sense BCH codes are Goppa codes with \(L=\{1,\alpha^{-1},\cdots,\alpha^{1-n}\}\) and \(G(x)=x^{\delta-1}\) [14; pg. 522].

Srivastava code

Generalized Srivastava codes are a special case of Goppa codes [16; Ch. 12].

References

[1]: V. D. Goppa, “A new class of linear error-correcting codes”, Probl. Peredach. Inform., vol. 6, no. 3, pp. 24-30, Sept. 1970.
[2]: V. D. Goppa, “Rational representation of codes and (Lg) codes”, Probl. Peredach. Inform., vol. 7, no. 3, pp. 41-49, Sept. 1971.
[3]: E. Berlekamp, “Goppa codes”, IEEE Transactions on Information Theory 19, 590 (1973) DOI
[4]: A. Couvreur, H. Randriambololona, “Algebraic Geometry Codes and Some Applications.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[5]: T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[6]: N. Patterson, “The algebraic decoding of Goppa codes”, IEEE Transactions on Information Theory 21, 203 (1975) DOI
[7]: Y. Sugiyama, M. Kasahara, S. Hirasawa, and T. Namekawa, “A method for solving key equation for decoding goppa codes”, Information and Control 27, 87 (1975) DOI
[8]: R. McEliece, The Theory of Information and Coding (Cambridge University Press, 2002) DOI
[9]: Daniel J. Bernstein, “Understanding binary-Goppa decoding.” Cryptology ePrint Archive (2022).
[10]: P. Beelen, T. Hoholdt, J. S. R. Nielsen, and Y. Wu, “On Rational Interpolation-Based List-Decoding and List-Decoding Binary Goppa Codes”, IEEE Transactions on Information Theory 59, 3269 (2013) DOI
[11]: R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, Technical report, Jet Propulsion Lab. DSN Progress Report (1978).
[12]: H. Janwa and O. Moreno, “McEliece public key cryptosystems using algebraic-geometric codes”, Designs, Codes and Cryptography 8, (1996) DOI
[13]: H. Randriambololona, “The syzygy distinguisher”, (2025) arXiv:2407.15740
[14]: W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[15]: T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) 317 DOI
[16]: F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[17]: A. Couvreur, “Codes and the Cartier Operator”, (2012) arXiv:1206.4728

Page edit log

Victor V. Albert (2022-08-21) — most recent
Victor V. Albert (2021-12-15)
Manasi Shingane (2021-12-14)

Cite as:

“Goppa code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/goppa

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/ag/residueAG/goppa.yml.