Goppa code[13] 

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

Children

Cousins

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) 317 DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: goppa

Cite as:
“Goppa code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/goppa
BibTeX:
@incollection{eczoo_goppa, title={Goppa code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/goppa} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/goppa

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.