In mathematics and computer science, the binary Goppa code is an error-correcting code that belongs to the class of general Goppa codes originally described by Valerii Denisovich Goppa, but the binary structure gives it several mathematical advantages over non-binary variants, also providing a better fit for common usage in computers and telecommunication. Binary Goppa codes have interesting properties suitable for cryptography in McEliece-like cryptosystems and similar setups.
Contents
Construction and properties
A binary Goppa code is defined by a polynomial
Codewords belong to the kernel of syndrome function, forming a subspace of
Code defined by a tuple
Note that this form of the parity-check matrix, being composed of a Vandermonde matrix
For practical purposes, parity-check matrix of a binary Goppa code is usually converted to a more computer-friendly binary form by a trace construction, that converts the
Decoding
Decoding of binary Goppa codes is traditionally done by Patterson algorithm, which gives good error-correcting capability (it corrects all
Patterson algorithm converts a syndrome to a vector of errors. The syndrome of a word
Alternative form of a parity-check matrix based on formula for
The algorithm then computes
Finally, the error locator polynomial is computed as
If the original codeword was decodable and the
Factoring or evaluating all roots of
Properties and usage
Binary Goppa codes viewed as a special case of Goppa codes have the interesting property that they correct full
Because of the high error correction capacity compared to code rate and form of parity-check matrix (which is usually hardly distinguishable from a random binary matrix of full rank), the binary Goppa codes are used in several post-quantum cryptosystems, notably McEliece cryptosystem and Niederreiter cryptosystem.