Cryptography Reference
In-Depth Information
The number of possible dyadic Goppa codes which can be produced by these
algorithm is the same as the number of distinct essences of dyadic signatures
corresponding to Cauchy matrices. This is about
lg
N
i
=0
2
i
). The algo-
rithm also produces equivalent essences where the elements corresponding to
the roots of the Goppa polynomial are only permuted. That leads to simple re-
ordering of those roots. As the Goppa polynomial itself is defined by its roots
regardless of their order, the actual number of possible Goppa polynomials is
(
q
−
lg
N
i
=0
2
i
)
/
(
(
q
−
lg
N
!).
2.4 Quasi-Dyadic Goppa Codes
A cryptosystem cannot be securely defined using completely dyadic Goppa codes
which admit a parity-check matrix in Cauchy form. By solving the overdefined
linear system
1
H
ij
=
z
i
+
L
j
with
nt
equations and
n
+
t
unknowns the Goppa
polynomial
G
(
x
) would be revealed immediately. Hence, Barreto and Misoczki
propose using binary Goppa codes in quasi-dyadic form for cryptographic appli-
cations.
Definition 4.
A quasi-dyadic matrix is a possibly non-dyadic block matrix whose
component blocks are dyadic submatrices.
A quasi-dyadic Goppa code over
F
2
s
for some
s
is obtained by constructing
a dyadic parity-check matrix
H
dyad
∈
F
F
p
=
t×n
q
F
2
m
of length
n
=
lt
where
n
is a multiple of the desired number of errors
t
, and then computing the
co-trace matrix
H
Tr
=
Tr
(
H
dyad
)
over
F
q
=
F
p
d
=
dt×n
p
. The resulting parity-check matrix
for the quasi-dyadic Goppa code is a non-dyadic matrix composed of blocks of
dyadic submatrices [16].
∈
F
3 Scheme Definition of QD-McEliece
The main difference between the original McEliece scheme and the quasi-dyadic
variant is the key generation algorithm 1 shown below. It takes as input the
system parameters
t
,
n
,and
k
and outputs a binary Goppa code in quasi-dyadic
form over a subfield
F
q
,where
p
=2
s
for some
s
,
q
=
p
d
=2
m
for some
d
with
m
=
ds
. The code length
n
must be a multiple of
t
such that
n
=
lt
for
some
l>d
.
The key generation algorithm proceeds as follows. It first runs
Algorithm
1in[16]
to produce a dyadic code
F
p
of
C
dyad
of length
N>>n
,where
N
is a
multiple of
t
not exceeding the largest possible length
q/
2. The resulting code
admits a
t
=
B
0
|···|
B
N/t−
1
which can be
×
N
parity-check matrix
H
dyad
viewed as a composition of
N/t
dyadic blocks
B
i
t
each. In the next
step the key generation algorithm uniformly selects
l
dyadic blocks of
H
dyad
of size
t
of size
t
×
×
t
each. This procedure leads to the same result as puncturing the
code
n
)
/t
first,
and then permuting the remaining
l
blocks by changing their order. The block
C
dyad
on a random set of block coordinates
T
t
of size (
N
−
