Cryptography Reference
In-Depth Information
Goppa codes in Tzeng-Zimmermann form.
It was shown by Tzeng and Zimmer-
mann [TZ75], that all Goppa codes with Goppa polynomial
g
(
x
)=
h
(
x
)
r
,for
some square-free
h
(
x
)andnumber
r>
0, admit a parity-check matrix consisting
solely of Cauchy power matrices over the splitting field of
g
(
x
).
Definition 3.
Let
be a finite field, and
β
=(
β
0
,β
1
...,β
t−
1
)
,γ
=(
γ
0
,γ
1
,...,
γ
n−
1
)
be two disjoint sequences of distinct elements in
F
F
.The
Cauchy matrix
C
(
β, γ
)
associated with these sequences is one where
C
i,j
=(
β
i
−
γ
j
)
−
1
, i.e.,
⎛
⎞
γ
0
)
−
1
γ
n−
1
)
−
1
(
β
0
−
···
(
β
0
−
⎝
.
.
⎠
C
=
.
γ
0
)
−
1
γ
n−
1
)
−
1
(
β
t−
1
−
···
(
β
t−
1
−
For any additional integer
r>
0
, the associated
Cauchy power matrix
C
(
β, γ, r
)
is a Cauchy matrix, where each coordinate is raised to the
r
-th power, i.e.,
C
i,j
=
(
β
i
−
γ
j
)
−r
.
Finally, the
Cauchy layered matrix
CL
(
β, γ, r
)
consists of all Cauchy power
matrices with exponents up to
r
, i.e.,
⎛
⎝
⎞
⎠
C
(
β, γ
)
C
(
β, γ,
2)
.
C
(
β, γ, r
)
CL
(
β, γ, r
)=
.
There is an ambivalence in this definition, i.e., there is no bijection from all
sequences
β
and
γ
to all Cauchy matrices. Specifically, for any
ω
∈
F
,wehave
C
(
β, γ
)=
C
(
β
+
ω, γ
+
ω
).
In terms of properties, Cauchy matrices are very similar to Vandermonde
matrices. For example, there are ecient algorithms to compute matrix-vector
products, submatrices of Cauchy matrices are again Cauchy, all Cauchy matrices
have full-rank, and there are closed formulas for computing their determinant.
As mentioned before, Tzeng and Zimmermann showed that all Goppa codes,
where the Goppa polynomial is the
r
-th power of an square-free polynomial,
admit a parity-check matrix which is a Cauchy layered matrix. This parity-
check matrix is in TZ form. Specifically, the parity-check matrix
H
in TZ form
of the Goppa code with support
L
=
{
γ
0
,...,γ
n−
1
}
and Goppa polynomial
g
(
x
)=
t−
1
β
i
)
r
is
H
=
CL
(
β, γ, r
).
This is particularly interesting for the case of wild Goppa codes as introduced
by Bernstein, Lange, and Peters [BLP10]. They show that if
r
divides the field
characteristic, then the rows of this TZ parity-check matrix are not linearly
independent, but the rows of
H
i
=0
(
x
−
1), where we omit the last
Cauchy block, are already a parity-check matrix of the full code. This allows wild
Goppa codes to achieve error-correcting capabilities surpassing general alternant
codes and make them particularly interesting for various application including
cryptography.
=
CL
(
β, γ, r
−
