- Source: Binary Goppa code
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.
Construction and properties
An irreducible binary Goppa code is defined by a polynomial
g
(
x
)
{\displaystyle g(x)}
of degree
t
{\displaystyle t}
over a finite field
G
F
(
2
m
)
{\displaystyle GF(2^{m})}
with no repeated roots, and a sequence
L
1
,
.
.
.
,
L
n
{\displaystyle L_{1},...,L_{n}}
of
n
{\displaystyle n}
distinct elements from
G
F
(
2
m
)
{\displaystyle GF(2^{m})}
that are not roots of
g
{\displaystyle g}
.
Codewords belong to the kernel of the syndrome function, forming a subspace of
{
0
,
1
}
n
{\displaystyle \{0,1\}^{n}}
:
Γ
(
g
,
L
)
=
{
c
∈
{
0
,
1
}
n
|
∑
i
=
1
n
c
i
x
−
L
i
≡
0
mod
g
(
x
)
}
{\displaystyle \Gamma (g,L)=\left\{c\in \{0,1\}^{n}\left|\sum _{i=1}^{n}{\frac {c_{i}}{x-L_{i}}}\equiv 0\mod g(x)\right.\right\}}
The code defined by a tuple
(
g
,
L
)
{\displaystyle (g,L)}
has dimension at least
n
−
m
t
{\displaystyle n-mt}
and
distance at least
2
t
+
1
{\displaystyle 2t+1}
, thus it can encode messages of length at least
n
−
m
t
{\displaystyle n-mt}
using codewords of size
n
{\displaystyle n}
while correcting at least
⌊
(
2
t
+
1
)
−
1
2
⌋
{\displaystyle \left\lfloor {\frac {(2t+1)-1}{2}}\right\rfloor }
errors. It possesses a convenient parity-check matrix
H
{\displaystyle H}
in form
H
=
V
D
=
(
1
1
1
⋯
1
L
1
1
L
2
1
L
3
1
⋯
L
n
1
L
1
2
L
2
2
L
3
2
⋯
L
n
2
⋮
⋮
⋮
⋱
⋮
L
1
t
−
1
L
2
t
−
1
L
3
t
−
1
⋯
L
n
t
−
1
)
(
1
g
(
L
1
)
1
g
(
L
2
)
1
g
(
L
3
)
⋱
1
g
(
L
n
)
)
{\displaystyle H=VD={\begin{pmatrix}1&1&1&\cdots &1\\L_{1}^{1}&L_{2}^{1}&L_{3}^{1}&\cdots &L_{n}^{1}\\L_{1}^{2}&L_{2}^{2}&L_{3}^{2}&\cdots &L_{n}^{2}\\\vdots &\vdots &\vdots &\ddots &\vdots \\L_{1}^{t-1}&L_{2}^{t-1}&L_{3}^{t-1}&\cdots &L_{n}^{t-1}\end{pmatrix}}{\begin{pmatrix}{\frac {1}{g(L_{1})}}&&&&\\&{\frac {1}{g(L_{2})}}&&&\\&&{\frac {1}{g(L_{3})}}&&\\&&&\ddots &\\&&&&{\frac {1}{g(L_{n})}}\end{pmatrix}}}
Note that this form of the parity-check matrix, being composed of a Vandermonde matrix
V
{\displaystyle V}
and diagonal matrix
D
{\displaystyle D}
, shares the form with check matrices of alternant codes, thus alternant decoders can be used on this form. Such decoders usually provide only limited error-correcting capability (in most cases
t
/
2
{\displaystyle t/2}
).
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
t
{\displaystyle t}
-by-
n
{\displaystyle n}
matrix over
G
F
(
2
m
)
{\displaystyle GF(2^{m})}
to a
m
t
{\displaystyle mt}
-by-
n
{\displaystyle n}
binary matrix by writing polynomial coefficients of
G
F
(
2
m
)
{\displaystyle GF(2^{m})}
elements on
m
{\displaystyle m}
successive rows.
Decoding
Decoding of binary Goppa codes is traditionally done by Patterson algorithm, which gives good error-correcting capability (it corrects all
t
{\displaystyle t}
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
c
=
(
c
1
,
…
,
c
n
)
{\displaystyle c=(c_{1},\dots ,c_{n})}
is expected to take a form of
s
(
x
)
≡
∑
i
=
1
n
c
i
x
−
L
i
mod
g
(
x
)
{\displaystyle s(x)\equiv \sum _{i=1}^{n}{\frac {c_{i}}{x-L_{i}}}\mod g(x)}
Alternative form of a parity-check matrix based on formula for
s
(
x
)
{\displaystyle s(x)}
can be used to produce such syndrome with a simple matrix multiplication.
The algorithm then computes
v
(
x
)
≡
s
(
x
)
−
1
−
x
mod
g
(
x
)
{\displaystyle v(x)\equiv {\sqrt {s(x)^{-1}-x}}\mod g(x)}
. That fails when
s
(
x
)
≡
0
{\displaystyle s(x)\equiv 0}
, but that is the case when the input word is a codeword, so no error correction is necessary.
v
(
x
)
{\displaystyle v(x)}
is reduced to polynomials
a
(
x
)
{\displaystyle a(x)}
and
b
(
x
)
{\displaystyle b(x)}
using the extended euclidean algorithm, so that
a
(
x
)
≡
b
(
x
)
⋅
v
(
x
)
mod
g
(
x
)
{\displaystyle a(x)\equiv b(x)\cdot v(x)\mod g(x)}
, while
deg
(
a
)
≤
⌊
t
/
2
⌋
{\displaystyle \deg(a)\leq \lfloor t/2\rfloor }
and
deg
(
b
)
≤
⌊
(
t
−
1
)
/
2
⌋
{\displaystyle \deg(b)\leq \lfloor (t-1)/2\rfloor }
.
Finally, the error locator polynomial is computed as
σ
(
x
)
=
a
(
x
)
2
+
x
⋅
b
(
x
)
2
{\displaystyle \sigma (x)=a(x)^{2}+x\cdot b(x)^{2}}
. 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
e
=
(
e
1
,
…
,
e
n
)
{\displaystyle e=(e_{1},\dots ,e_{n})}
was the binary error vector, then
σ
(
x
)
=
∏
i
=
1
n
e
i
(
x
−
L
i
)
{\displaystyle \sigma (x)=\prod _{i=1}^{n}e_{i}(x-L_{i})}
Factoring or evaluating all roots of
σ
(
x
)
{\displaystyle \sigma (x)}
therefore gives enough information to recover the error vector and fix the errors.
Properties and usage
Binary Goppa codes viewed as a special case of Goppa codes have the interesting property that they correct full
deg
(
g
)
{\displaystyle \deg(g)}
errors, while only
deg
(
g
)
/
2
{\displaystyle \deg(g)/2}
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 cryptosystems, 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. MR2345114. 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
See also
BCH codes
Code rate
Reed–Solomon error correction
Kata Kunci Pencarian:
- Binary Goppa code
- Linear code
- McEliece cryptosystem
- Post-quantum cryptography
- Index of cryptography articles
- List of algebraic coding theory topics
- BCH code
- Niederreiter cryptosystem
- Valery Goppa
- Reed–Solomon error correction
