Also known as LG code.
Description
Let \( G(x) \) be a polynomial describing a projective-plane curve with coefficients from \( GF(q^m) \) for some fixed integer \(m\). Let \( L \) be a finite subset of the extension field \( GF(q^m) \) where \(q\) is prime, meaning \( L = \{\alpha_1, \cdots, \alpha_n\} \) is a subset of nonzero elements of \( GF(q^m) \). A Goppa code \( \Gamma(L,G) \) is an \([n,k,d]_q\) linear code consisting of all vectors \(a = a_1, \cdots, a_n\) such that \( R_a(x) =0 \) modulo \(G(x)\), where \( R_a(x) = \sum_{i=1}^n \frac{a_i}{z - \alpha_i} \).
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 \( n = |L| \) , dimension \( k \geq n-mr \) where \( r = \text{deg} G(x) \), and the minimum distance \( 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 \(GF(q)\) that are not roots of \(G\). It returns a Goppa code.
Parents
- Residue AG code
- Cartier code — Goppa codes are Cartier codes from a curve of genus zero [14].
- Alternant code — Goppa codes are a special case of alternant codes [15; Ch. 12].
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}\) [16; pg. 522].
- Srivastava code — Generalized Srivastava codes are a special case of Goppa codes [15; Ch. 12].
Cousins
- Generalized RS (GRS) code — Goppa codes are \(GF(q)\)-subfield subcode of the dual of the GRS code over \(GF(q^m)\) with evaluation points \(\alpha_i\) and factors \(v_i=G(\alpha_i)^{-1}\) ([16], pg. 523; [5]).
- \(q\)-ary linear LTC — Goppa codes are locally testable [17].
- Quantum Goppa code — Classical Goppa codes over various algebraic curves are used to construct quantum Goppa codes.
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 et al., “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 et al., “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”, (2024) arXiv:2407.15740
- [14]
- A. Couvreur, “Codes and the Cartier Operator”, (2012) arXiv:1206.4728
- [15]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [16]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [17]
- T. Kaufman and S. Litsyn, “Almost Orthogonal Linear Codes are Locally Testable”, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05) DOI
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