Cryptography Reference
In-Depth Information
Algorithm 1.
QD-McEliece: Key generation algorithm
Input:
Fixed common system parameters:
t
,
n
=
l · t
,
k
=
n − dt
Output:
private key
K
pr
, public key
K
pub
1: (
L
dyad
,
η
)
←
Algorithm 1 in [16]
(2
m
,N,t
), where
G
(
x
)
H
dyad
,
N>>n
,
N
=
l
· t<q/
2
2: Select uniformly at random
distinct blocks
B
i
0
|···|B
i
l
−
1
in any order from
l
H
dyad
3: Select
l
dyadic permutations
Π
j
0
, ··· ,Π
j
l
−
1
of size
t × t
each
4: Select
l
nonzero scale factors
σ
0
,...,σ
l−
1
∈
F
p
.If
p
= 2, then all scale factors are
equal to 1.
5: Compute
H
=
B
i
0
Π
j
0
|···|B
i
l
−
1
Π
j
l
−
1
∈
F
t×t
q
)
l
(
6: Compute
Σ
=
Diag
(
σ
0
I
t
,...,σ
l−
1
I
t
)
∈
(
F
t×t
p
)
l×l
7: Compute the co-trace matrix
H
Tr
=
Tr
(
HΣ
)=
Tr
(
H
)
Σ ∈
(
F
t×t
)
l×l
8: Bring
H
Tr
in systematic form
H
=[
Q|I
n−k
], e.g. by means of Gaussian elimination
p
9: Compute the public generator matrix
G
=[
I
k
|Q
T
]
10:
return
K
pub
=(
ˆ
G
,
t
),
K
pr
=(
H
dyad
,
L
dyad
,
η
,
G
(
x
), (
i
0
,...,i
l−
1
), (
j
0
,...,j
l−
1
),
(
σ
0
,...,σ
l−
1
))
permutation sequence (
i
0
,...,i
l
) is the first part of the trapdoor information. It
can also be described as an
N
×
n
permutation matrix
P
B
. Then the selection and
permutation of
t
P
B
.
Further transformations performed to disguise the structure of the private code
are dyadic inner block permutations.
Definition 5.
A
dyadic permutation
Π
j
×
t
blocks can be done by right-side multiplication
H
dyad
×
is a dyadic matrix whose signature is
the
j
-th row of the identity matrix. A dyadic permutation is an involution, i.e.
(
Π
j
)
2
=
I
.The
j
-th row (or equivalently the
j
-th column) of the dyadic matrix
defined by a signature
h
can be written as
Δ
(
h
)
j
=
hΠ
j
.
The key generation algorithm first chooses a sequence of integers (
j
0
,...,j
l−
1
)
defining the positions of ones in the signatures of the
l
dyadic permutations.
Then each block
B
i
is multiplied by a corresponding dyadic permutation
Π
j
to obtain a matrix
H
which defines a permutation equivalent code
C
H
to the
T
t
punctured code
C
dyad
. Since the dyadic inner-block permutations can be com-
n
permutation matrix
P
dp
=
Diag
(
Π
j
0
,
,Π
j
l
−
1
)wecanwrite
bined to an
n
×
···
H
=
H
dyad
·
P
B
·
P
dp
. The last transformation is scaling. Therefore, first a sequence
(
σ
0
,...,σ
l−
1
)
F
p
is chosen, and then each dyadic block of
H
is multiplied by
a diagonal matrix
σ
i
I
t
such that
H
=
H
∈
Σ
. Finally, the
co-trace construction derives from
H
the parity-check matrix
H
Tr
for a binary
quasi-dyadic permuted subfield subcode over
·
Σ
=
H
dyad
·
P
B
·
P
dp
·
F
p
.Bringing
H
Tr
in systematic
form, e.g. by means of Gaussian elimination, we obtain a systematic parity-
check matrix
H
for the public code.
H
is still a quasi-dyadic matrix composed
of dyadic submatrices which can be represented by a signature of length
t
each
and which are no longer associated to a Cauchy matrix. The generator matrix
G
H
defines the public code
obtained from
C
pub
of length
n
and dimension
k
over
F
p
, while
H
defines a dual code
C
pub
of length
n
and dimension
k
=
n
−
dt
.The
