Cryptography Reference
In-Depth Information
G
(
x
)=
i
=0
g
i
x
i
of degree
t
with coecients taken in a finite field
F
q
where
n
q
, whose elements
L
i
are not roots
of
G
(
x
). Lower bounds on their dimension and minimum distance are known, as
well as an e
cient polynomial-time decoding algorithm.
q
=2
m
and a subset
L
=(
L
0
,...,L
n−
1
)
∈
F
n
q
Theorem 1.
Let
L
be a sequence
L
=(
L
0
,...,L
n−
1
)
∈
F
of distinct elements
and
G
(
x
)
a Goppa polynomial of degree
t
where
G
(
L
i
)
=0
,
∀
0
≤
i
≤
n
−
1
.For
p
we define the
syndrome
of
c
by
any vector
c
=(
c
0
,...,c
n−
1
)
∈
F
n−
1
n−
1
c
i
G
(
L
i
)
G
(
x
)
−
G
(
L
i
)
c
i
S
c
(
x
)=
−
mod
G
(
x
)
≡
mod
G
(
x
)
.
x
−
L
i
x
−
L
i
i
=0
i
=0
n
p
.
The
binary Goppa code
Γ
(
L, G
(
x
))
is defined as the following subspace of
F
n
p
Γ
(
L, G
(
x
)) =
{
c
∈
F
|
S
c
(
x
)
≡
0mod
G
(
x
)
}
An alternative way to define Goppa codes is to treat them as subfield subcodes
of Generalized Reed-Solomon codes. In that special case Goppa codes are also
called alternant codes.
n
q
Definition 1.
Given a sequence
L
=(
L
0
,...,L
n−
1
)
∈
F
of distinct elements
n
and a sequence
D
=(
D
0
,...,D
n−
1
)
q
of nonzero elements, the Generalized
Reed-Solomon code
GRS
t
(
L, D
)
is the [n,k,t+1] linear error-correcting code de-
fined by the parity-check matrix
H
L,D
=
vdm
(
t, L
)
∈
F
·
Diag
(
D
)
where
vdm
(
t, L
)
n
Vandermonde matrix with elements
vdm
ij
=
L
j
.
denotes the
t
×
⎛
⎞
D
0
D
1
···
D
n−
1
⎝
⎠
D
0
L
0
D
1
L
1
···
D
n−
1
L
n−
1
H
L,D
:=
.
.
.
.
.
.
D
0
L
t−
1
D
1
L
t−
1
D
n−
1
L
t−
1
···
0
1
n−
1
In the original McEliece cryptosystem binary irreducible Goppa codes are
used. A Goppa code is
if the used Goppa polynomial
G
(
x
) is irre-
irreducible
F
q
. In this case the Goppa code can correct up to
t
errors.
ducible over
If
G
(
x
)=
t−
1
i
=0
(
x
−
z
i
) is a monic polynomial with
t
distinct
roots all in
F
q
F
q
.Incaseof
q
=2
m
the Goppa code can also
correct
t
errors. A Goppa code generated by a separable polynomial over
then it is called
separable
over
F
q
admits a parity-check matrix in Cauchy form [14].
t
q
Definition 2.
Given two disjoint sequences
z
=(
z
0
,...,z
t−
1
)
∈
F
and
L
=
n
q
(
L
0
,...,L
n−
1
)
∈
F
of distinct elements, the Cauchy matrix
C
(
z, L
)
is the
t
×
n
matrix with elements
C
ij
=1
/
(
z
i
−
L
j
)
.
Theorem 2.
The Goppa code generated by a monic polynomial
G
(
x
)=(
x
−
z
0
)
z
t−
1
)
without multiple zeros admits a parity-check matrix of the form
H
=
C
(
z, L
)
, i.e.
H
ij
=1
/
(
z
i
−
···
(
x
−
L
j
)
,
0
≤
i<t,
0
≤
j<n
.
