Cryptography Reference
In-Depth Information
Table 7.
Comparison of the quasi-dyadic McEliece variant including KIC-
γ
(n'=2312,
k'=1288, t=64) with original McEliece PKC (n=2048, k=1751, t=27), ECC-P160, and
RSA-1024
Method
Time Throughput
sec
bits/sec
QD-McEliece encryption
0.1987
6482
QD-McEliece decryption (with
S
)
1.0480
1229
QD-McEliece decryption (on-the-fly) 1.5676
822
McEliece encryption [6]
0.4501
3889
McEliece decryption [6]
0.6172
2835
ECC-160 [10]
0.2025
790
RSA-1024 2
16
+ 1 [10]
0.1075
9525
RSA-1024 w. CRT [10]
2.7475
373
As we could not store the log- and antilog tables for this field in the Flash mem-
ory, we had to implement the tower field arithmetic which significantly reduces
performance. For instance, one multiplication over a tower
F
(2
8
)
2
involves 5 mul-
tiplications over the subfield
F
2
8
. Hence, much more arithmetic operations have
to be performed to decrypt a ciphertext.
Nevertheless, the decryption function is still faster than the RSA-1024 private
key operation and exceeds the throughput of ECC-160. Furthermore, although
slower, the on-the-fly decoding algorithm requires 81% less memory compared to
the original McEliece version such that migration to cheaper devices is possible.
6 Conclusion and Further Research
In this work we have implemented a McEliece variant based on quasi-dyadic
Goppa codes on a 8-bits AVR microcontroller. The family of quasi-dyadic Goppa
codes offers the advantage of having a compact and simple description. Using
quasi-dyadic Goppa codes the public key for the McEliece encryption is signifi-
cantly reduced. Furthermore, we used a generator matrix for the public code in
systematic form resulting in an additional key reduction. As a result, the public
key size is a factor
t
less compared to generic Goppa codes used in the original
McEliece PKC. Moreover, the public key can be kept in this compact size not
only for storing but for processing as well. However, the systematic coding neces-
sitates further conversion to protect the message. Without any conversions the
encrypted message would be revealed immediately from the ciphertext. Hence,
we have implemented Kobara-Imai's specific conversion
γ
: a conversion scheme
developed specially for CCA2 secure McEliece variants.
Our implementation out performs the implementations of the original McEliece
PKC and ECC-160 in encryption. In particular, the quasi-dyadic McEliece en-
cryption is 2.3 times faster than the original McEliece PKC and exceeds the
throughput of both, the original McEliece PKC and ECC-160, by 1.7 and 8.2
