Cryptography Reference
In-Depth Information
of embedded microcontrollers is restricted to 8 bits it is advisable to construct
subfield subcodes of codes over
F
2
8
or
F
2
16
. But the extension field
F
2
8
is too
small to derive secure subfield subcodes from codes defined over it.
Over the base subfield
F
2
of
F
2
16
[16] suggests using the parameters summa-
rized in Table 2.
Table 2.
Suggested parameters for McEliece variants based on quasi-dyadic Goppa
codes over
F
2
level t n=l
·
t k=n-m
·
t key size
(
m · k
bits)
80 2
6
36
·
2
6
= 2304 20
·
2
6
= 1280 20
·
2
10
bits = 20 Kbits
112 2
7
28
·
2
7
= 3584 12
·
2
7
= 1536 12
·
2
11
bits = 24 Kbits
128 2
7
32
·
2
7
= 4096 16
·
2
7
= 2048 16
·
2
11
bits = 32 Kbits
192 2
8
28
·
2
8
= 7168 12
·
2
8
= 3072 12
·
2
12
bits = 48 Kbits
256 2
8
32
·
2
8
= 8192 16
·
2
8
= 4096 16
·
2
12
bits = 64 Kbits
G
is in systematic form, only its non-trivial
As the public generator matrix
part
Q
of length
n
−
k
=
m
·
t
has to be stored. This part consists of
m
(
l
−
m
)
dyadic submatrices of size
t
t
each. Storing only the
t
-length signatures of
Q
,
the resulting public key size is
m
(
l
×
k
bits in size. Hence, the public
key size is a factor of
t
smaller compared to the generic McEliece version where
the key even in systematic form is (
n
−
m
)
t
=
m
·
−
k
)
·
k
bits in size.
3.2 Security of QD-McEliece
A recent work [7] presents an ecient attack recovering the private key in spe-
cific instances of the quasi-dyadic McEliece variant. Due to the structure of a
quasi-dyadic Goppa code additional linear equations can be constructed. These
equations reduce the algebraic complexity of solving a multidimensional system
of equations using Groebner bases [1]. In the case of the quasi-dyadic McEliece
variant there are
l
−
m
linear equations and
l
−
1 unknowns
Y
i
. The dimension of
the vector space solution for the
Y
i
s
is
m
1. Once the unknowns
Y
i
are found
all other unknowns
X
i
can be obtained by solving a system of linear equations.
In our case there are 35 unknowns
Y
i
, 20 linear equations, and the dimension of
the vector space solution for the
Y
i
s
is 15. The authors remark that the solution
space is manageable in practice as long as
m<
16. The attack was not successful
with
m
= 16. Hence, up to now the McEliece variant using subfield subcodes
over the base field of large codes over
−
F
2
16
is still secure.
3.3 Conversions for CCA2-Secure McEliece Variants
In [13] Kobara and Imai considered conversions for achieving CCA2-security
in a restricted class of public-key cryptosystems. The authors reviewed these
conversions for applicability to the McEliece public key cryptosystem and showed