Binary Goppa code: Difference between revisions

Revision as of 00:36, 7 December 2012

Latest revision as of 17:54, 18 January 2025

(35 intermediate revisions by 25 users not shown)

Line 1:

{{Short description|Kind of error correction code}}

In [[mathematics]] and [[computer science]], the '''binary Goppa code''' is an [[error-correcting code]] that belongs to the class of general [[Goppa code]]scodes 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 cryptosystem|McEliece-like cryptosystems]] and similar setups.

==Construction and properties==

BinaryAn irreducible binary Goppa code is defined by a [[polynomial]] <math>g(x)</math> of degree <math>t</math> over a [[finite field]] <math>GF(2^m)</math> withoutwith multipleno zerosrepeated roots, and a sequence <math>LL_1, ..., L_n</math> of <math>n</math> distinct elements from <math>GF(2^m)</math> that aren'tare not roots of the polynomial:<math>g</math>.

Codewords belong to the kernel of the syndrome function, forming a subspace of <math>\{0,1\}^n</math>:

: <math>\forall i,j \in \mathbb{Z}_n: L_i \in GF(2^m) \and L_i \neq L_j \and g(L_i) \neq 0</math>

: <math>\Gamma(g,L)=\left\{ c \in \{0,1\}^n \,\Bigg\vert\, \sum_{i=1}^n \frac{c_i}{x-L_i} \equiv 0 \bmod g(x) \right\}</math>

Code defined by a tuple <math>(g,L)</math> has minimum distance <math>2t-1</math>, thus it can correct <math>t</math> errors in a word of size <math>n-mt</math> using codewords of size <math>n</math>. It possesses a [[parity-check matrix]] <math>H</math> in form

The code defined by a tuple <math>(g,L)</math> has dimension at least <math>n-mt</math> and

Codedistance definedat by a tuple <math>(g,L)</math> has minimum distanceleast <math>2t-+1</math>, thus it can correctencode messages of length at least <math>tn-mt</math> errorsusing in a wordcodewords of size <math>n-mt</math> usingwhile codewordscorrecting ofat sizeleast <math>n\left\lfloor \frac{(2t+1)-1}{2} \right\rfloor</math> errors. It possesses a convenient [[parity-check matrix]] <math>H</math> in form

: <math>

H=VD=\begin{pmatrix}

1 & 1 & 1 & \cdots & 1\\

L_0L_1^1 & L_1L_2^1 & L_2L_3^1 & \cdots & L_{n-1}^1\\

L_0L_1^2 & L_1L_2^2 & L_2L_3^2 & \cdots & L_{n-1}^2\\

\vdots & \vdots & \vdots & \ddots & \vdots \\

L_0L_1^{t-1} & L_1L_2^{t-1} & L_2L_3^{t-1} & \cdots & L_{n-1}^{t-1}

\end{pmatrix}

\begin{pmatrix}

\frac{1}{g(L_0L_1)} & & & & \\

& \frac{1}{g(L_1L_2)} & & & \\

& & \frac{1}{g(L_2L_3)} & & \\

& & & \ddots & \\

& & & & \frac{1}{g(L_{n-1})}

\end{pmatrix}

</math>

Note that this form of the parity-check matrix, being composed of a [[Vandermonde matrix]] <math>V</math> and [[diagonal matrix]] <math>D</math>, shares the form with check matrices of [[generalized Reed–Solomonalternant code]]s, thus GRS (and also BCH)alternant decoders can be used on this form. Such decoders usually provide only limited error-correcting capability (in most cases <math>t/2</math>).

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 <math>t</math>-by-<math>n</math> matrix over <math>GF(2^m)</math> to a <math>mt</math>-by-<math>n</math> binary matrix by writing polynomial cofficientscoefficients of <math>GF(2^m)</math> elements on <math>m</math> successive rows.

==Decoding==

Decoding of binary Goppa codes is traditionalytraditionally done by Patterson algorithm, which gives good error-correcting capability (it corrects all <math>t</math> design errors), and is also fairly simple to implement.

Patterson algorithm converts a syndrome to a vector of errors. The syndrome of a binary word <math>c=(c_0c_1,\dots,c_{n-1}c_n)</math> is expected to take a form of

: <math>s(x) =\equiv \sum_{c_ii=1}^n \frac{1c_i}{x - L_i} \mod g(x)</math>

Alternative form of a parity-check matrix based on formula for <math>s(x)</math> can be used to produce such syndrome with a simple matrix multiplication.

The algorithm then computes <math>v(x)= \equiv \sqrt{s(x)^{-1}-x} \mod g(x)</math>. That fails when <math>s(x)= \equiv 0</math>, but that is the case when the input word is a codeword, so no error correction is necessary.

<math>v(x)</math> is reduced to polynomials <math>a(x)</math> and <math>b(x)</math> using the [[extended euclidean algorithm]], so that <math>a(x)= \equiv b(x)\cdot v(x) \mod g(x)</math>, while <math>\deg(a)\leq\lfloor t/2 \rfloor</math> and <math>\deg(b)\leq\lfloor (t-1)/2 \rfloor</math>.

Finally, the ''error correctionlocator polynomial'' is computed as <math>\sigma(x) = a(x)^2 + x\cdot b(x)^2</math>. Note that in binary case, locating the errors is sufficient to correct them, as there's only one other value possible. In non-binary cases a separate error correction polynomial has to be computed as well.

If the original codeword was decodable and the <math>e=(e_0,e_1,\dots,e_{n-1}e_n)</math> was the binary error vector, then

: <math>\sigma(x) = \prod_{e_ii=1}^n (x-L_i)^{e_i} </math>

Factoring or evaluating all roots of <math>\sigma(x)</math> therefore gives enough information to recover the error vector and fix the errors.

Line 56 ⟶ 60:

Binary Goppa codes viewed as a special case of Goppa codes have the interesting property that they correct full <math>\deg(g)</math> errors, while only <math>\deg(g)/2</math> errors in ternary and all other cases. Asymptotically, this error correcting capability meets the famous [[Gilbert–Varshamov bound]].

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]] [[cryptosystem|cryptosystems]]s, notably [[McEliece cryptosystem]] and [[Niederreiter cryptosystem]].

==References==

* Elwyn R. Berlekamp, Goppa Codes, IEEE Transactions on information theory, Vol. IT-19, No. 5, September 1973, https://web.archive.org/web/20170829142555/http://infosec.seu.edu.cn/space/kangwei/senior_thesis/Goppa.pdf

* Daniela Engelbert, Raphael Overbeck, Arthur Schmidt. "A summary of McEliece-type cryptosystems and their security." Journal of Mathematical Cryptology 1, 151–199. {{MR 2008h:94056|2345114}}. Previous version: http://eprint.iacr.org/2006/162/

* Daniel J. Bernstein. "List decoding for binary Goppa codes." http://cr.yp.to/codes/goppalist-20110303.pdf