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 Reed Solomon 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].Guruswami-Sudan list decoder [9].Binary Goppa codes can be decoded using a RS-based decoder [10].
Realizations
Initial version of the McEliece public-key cryptosystem [11][12] and its variation by Niederreiter [13] where the generator matrix is replaced by the parity check matrix. Some of these were proven to be insecure since the public key exposes algebraic structure of code [14].
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
- 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}\) ([15], pg. 523; [5]).
- Cartier code — Goppa codes are Cartier codes from a curve of genus zero [16].
Cousins
- \(q\)-ary linear LTC — Goppa codes are locally testable [17].
- Bose–Chaudhuri–Hocquenghem (BCH) code — Narrow-sense BCH codes are Goppa codes with \(L=\{1,\alpha^{-1},\cdots,\alpha^{1-n}\}\) and \(G(x)=x^{\delta-1}\) ([15], pg. 522).
- Binary quantum Goppa code — Classical Goppa codes are used to construct their quantum versions.
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]
- W. C. Huffman, J.-L. Kim, and P. Solé, 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]
- V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometric codes”, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) DOI
- [10]
- Daniel J. Bernstein, "Understanding binary-Goppa decoding." Cryptology ePrint Archive (2022).
- [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. Niederreiter (1986). Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory. Problemy Upravlenija I Teorii Informacii. 15: 159–166.
- [14]
- V. M. SIDELNIKOV and S. O. SHESTAKOV, “On insecurity of cryptosystems based on generalized Reed-Solomon codes”, Discrete Mathematics and Applications 2, (1992) DOI
- [15]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [16]
- A. Couvreur, “Codes and the Cartier Operator”, (2012) arXiv:1206.4728
- [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:
“Classical Goppa code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/goppa