Cryptography Reference
In-Depth Information
trapdoor information consisting of the essence
η
of the signature
h
dyad
,these-
quence (
i
0
,...,i
l−
1
) of blocks, the sequence (
j
0
,...,j
l−
1
) of dyadic permutation
identifiers, and the sequence of scale factors (
σ
0
,...,σ
l−
1
) relates the public code
defined by
H
with the private code defined by
H
dyad
. The public code defined by
G
admits a further parity-check matrix
V
L
∗
,G
=
vdm
(
L
∗
,G
(
x
))
·
Diag
(
G
(
L
i
)
−
1
)
where
L
∗
is the permuted support obtained from
L
dyad
by
L
∗
=
L
dyad
·
P
db
.
Bringing
V
L
∗
,G
in systematic form leads to the same quasi-dyadic parity-check
matrix
H
for the code
P
B
·
C
pub
.Thematrix
V
L
∗
,G
is permutation equivalent to the
parity-check matrix
V
L,G
=
vdm
(
L, G
(
x
))
·
Diag
(
G
(
L
i
)
−
1
) for the shortened pri-
T
t
dyad
vate code
C
pr
=
C
obtained by puncturing the large private code
C
dyad
on
the set of block coordinates
T
t
. The support
L
for the code
C
pr
is obtained by
deleting all components of
L
dyad
at the positions indexed by
T
t
. Classical irre-
ducible Goppa codes use support sets containing all elements of
F
q
.Thus,the
support corresponding to such a Goppa code can be published while only the
Goppa polynomial and the (support) permutation are parts of the secret key. In
contrast, the support sets
L
and
L
∗
for
C
pr
and
C
pub
, respectively, are not full
F
q
where
L
∗
is a permuted version of
L
. Hence, the support
sets contain additional information and have to be kept secret.
The encryption algorithm of the QD-McEliece variant is the same as that of
the original McEliece cryptosystem. First a message vector is multiplied by the
systematic generator matrix
but just subsets of
G
for the quasi-dyadic public code
C
pub
to obtain the
corresponding codeword. Then a random error vector of length
n
and hamming
weight at most
t
is added to the codeword to obtain a ciphertext.
The decryption algorithm of the QD-McEliece version is essentially the same
as that of the classical McEliece cryptosystem. The following decryption strate-
gies are conceivable.
Permute the ciphertext and undo the inner block dyadic permutation as well
astheblockpermutationtoobtainanextendedpermutedciphertextoflength
N
such that
ct
perm
=
ct
·
P
B
·
P
dp
. Then use the decoding algorithm of the large
private code
C
dyad
to obtain the corresponding codeword. Multiplying
ct
perm
by the parity-check matrix for
C
dyad
yields the same syndrome as reversing the
dyadic permutation and the block permutation without extending the length of
the ciphertext and using a parity-check matrix for the shortened private code
C
pr
.
A better method is to decrypt the ciphertext directly using the equivalent parity-
check matrix
V
L
∗
,G
for syndrome computation. Patterson's decoding algorithm
can be used to detect the error and to obtain the corresponding codeword. Since
G
is in systematic form, the first
k
bits of the resulting codeword correspond to
the encrypted message.
3.1 Parameter Choice and Key Sizes
For an implementation on an embedded microcontroller the best choice is to use
Goppa codes over the base field
F
2
. In this case the matrix vector multiplication
can be performed most eciently. Hence, the subfield
F
2
s
should be chosen
to be the base field itself where
s
=1and
p
= 2. Furthermore, as the register size
F
p
=
