Cryptography Reference
In-Depth Information
2.3 Dyadic Goppa Codes
In [16] Barreto and Misoczki show how to build binary Goppa codes which admit
a parity-check matrix in dyadic form. The family of dyadic Goppa codes offers
the advantage of having a compact and simple description. In their proposal the
authors make extensive use of the fact that using Goppa polynomials separable
over
F
q
the resulting Goppa code admits a parity-check matrix in Cauchy form
by Theorem 2. Hence, it is possible to construct parity-check matrices which are
in Cauchy and dyadic form, simultaneously.
Definition 3.
Let
F
q
denote a finite field and
h
=(
h
0
,h
1
,...,h
n−
1
)
∈
F
q
a
n
q
is the symmetric matrix
with elements
Δ
ij
=
h
i⊕j
,where
⊕
is the bitwise exclusive-or. The sequence
h
is
cal led
signature
of
Δ
(
h
)
and coincides with the first row of
Δ
(
h
)
. Given
t>
0
,
Δ
(
h, t
)
denotes
Δ
(
h
)
truncated to its first
t
rows.
sequence of
F
q
elements. The
dyadic matrix
Δ
(
h
)
∈
F
When
n
isapowerof2every1
×
1 matrix is a dyadic matrix, and for
k>
0any
2
k
matrix
Δ
(
h
)isoftheform
Δ
(
h
):=
AB
BA
where
A
and
B
are dyadic
2
k
×
2
k−
1
×
2
k−
1
matrices.
n×n
q
Theorem 3.
Let
H
∈
F
with
n>
1
be a dyadic matrix
H
=
Δ
(
h
)
for some
q
q
signature
h
∈
F
and a Cauchy matrix
C
(
z, L
)
for two disjoint sequences
z
∈
F
q
and
L
∈
F
of distinct elements, simultaneously. It follows that
-
F
q
is a field of characteristic 2
-
h
satisfies
+
1
h
0
-
the elements of
z
are defined as
z
i
=
1
h
i
⊕
j
1
h
i
1
h
j
=
+
1
h
i
+
ω
,and
1
h
j
1
h
0
-
the elements of
L
are defined as
L
i
=
+
+
ω
for some
ω
∈
F
q
It is obvious that a signature
h
describing such a dyadic Cauchy matrix cannot be
chosen completely at random. Hence, the authors suggest only choosing nonzero
distinct
h
0
and
h
i
at random, where
i
scans all powers of two smaller than
n
,
and to compute all other values for
h
by
h
i⊕j
=
1
for 0
<j<i
.
Algorithm 1 in [16] shows how binary dyadic Goppa codes are constructed. It
takes as input three integers:
q
,
N
,and
t
. The first integer
q
=
p
d
=2
m
where
m
=
s
1
h
i
+
h
j
+
h
0
·
d
defines the finite field
F
q
as degree
d
extension of
F
p
=
F
2
s
. The code
length
N
is a power of two such that
N
q/
2. The integer
t
denotes the number
of errors correctable by the Goppa code. The algorithm outputs the support
L
,
a separable polynomial
G
(
x
), as well as the dyadic parity-check matrix
H
≤
∈
t×N
q
for the binary Goppa code
Γ
(
L, G
(
x
)) of length
N
and designed minimum
distance 2
t
+1.
Furthermore, Algorithm 1 in [16] generates the essence
η
of the signature
h
of
H
where
η
r
F
1
h
2
r
1
h
0
1
h
0
=
+
for
r
=0
,...,
lg
N
−
1with
η
lg
N
=
,sothat,
for
i
=
lg
N−
1
k
=0
=
η
lg
N
+
lg
N−
1
i
k
2
k
,
1
h
i
i
k
η
k
. The first
lg
t
elements
k
=0
of
η
together with
completely specify the roots of the Goppa polynomial
G
(
x
), namely,
z
i
=
η
lg
N
+
lg
t−
1
k
=0
lg
N
i
k
η
k
.
