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
 
Search WWH ::




Custom Search