Cryptography Reference
In-Depth Information
times, respectively. In addition, our encryption algorithm requires 96,7% less
memory compared to the original McEliece version and can be migrated to much
cheaper devices.
The performance of the McEliece decryption algorithm is closely related to
the number of errors added within the encryption. In our case the number of
errors is 64 which is 2.4 times greater compared to the original McEliece PKC.
Hence, the polynomials used are huge and the parity-check matrix is too large
to be completely precomputed and stored in the Flash memory. In addition, the
error correction requires more time because a polynomial of degree 64 has to
be evaluated. We showed in Section 4.2 that none of the frequently used error
correction algorithms, such as the Berlekamp trace algorithm and the Chien
search, are suitable for punctured and shortened codes obtained from codes over
very large fields. Furthermore, the tower field arithmetic significantly reduces the
performance of the decoding algorithm. Nevertheless, the decryption algorithms
with precomputation and on-the-fly computation are 2.6 and 1.8 times faster
than the RSA-1024 private key operation and exceed 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.
Acknowledgement.
I would like to thank Olga Paustjan and Paulo Barreto
for fruitful discussions. Special thanks to an anonymous reviewer for many useful
comments.
References
1. Adams, W., Loustaunau, P.: An Introduction to Grobner Bases, vol. 3 (1994)
2. Afanasyev, V.B.: On the complexity of finite field arithmetic. In: Fifth Joint Soviet-
Swedish Intern. Workshop Information Theory, pp. 9-12 (January 1991)
3. Berlekamp, E.R.: Factoring polynomials over large finite fields. Mathematics of
Computation 24(111), 713-715 (1970)
4. Bernstein, D.J., Lange, T., Peters, C.: Attacking and Defending the McEliece Cryp-
tosystem. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp.
31-46. Springer, Heidelberg (2008)
5. Chien, R.: Cyclic decoding procedure for the bose-chaudhuri-hocquenghem codes.
IEEE Transactions on Information Theory IT-10(10), 357-363 (1964)
6. Eisenbarth, T., Guneysu, T., Heyse, S., Paar, C.: MicroEliece: McEliece for Em-
bedded Devices. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp.
49-64. Springer, Heidelberg (2009)
7. Faugere, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: Algebraic Cryptanalysis of
McEliece Variants with Compact Keys. In: Gilbert, H. (ed.) EUROCRYPT 2010.
LNCS, vol. 6110, pp. 279-298. Springer, Heidelberg (2010)
8. Fujisaki, E., Okamoto, T.: Secure Integration of Asymmetric and Symmetric En-
cryption Schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537-
554. Springer, Heidelberg (1999)
9. Goppa, V.D.: A New Class of Linear Correcting Codes. Probl. Pered. Info. 6(3),
24-30 (1970)
