Implementation of McEliece Based on Quasi-dyadic Goppa Codes for Embedded Devices

Most public-key cryptosystems frequently implemented have been proven secure on the basis of the presumed hardness of two mathematical problems: factoring the product of two large primes (FP) and computing discrete logarithms (DLP). At present, both problems are believed to be computationally infeasible with an ordinary computer. However, a quantum-computer having the ability to perform computations on a few thousand qbits could solve both problems using Shor’s algorithm [23]. Although a quantum computer of this dimension has not been reported, development and cryptanalysis of alternative public-key cryptosystems seem suitable. To achieve acceptance and attention in practice, they have to be implemented efficiently. Furthermore, the implementations have to perform fast while keeping memory requirements low for security levels comparable to conventional schemes. The McEliece encryption and decryption do not require computationally expensive multiple precision arithmetic. Hence, it is predestined for an implementation on embedded devices. The major disadvantage of the McEliece public-key cryptosystem(PKC) is its very large public key of several hundred thousands bits. For this reason, the McEliece PKC has achieved little attention in the practice. Another disadvantage of the McEliece scheme, like many other schemes, is that it is not semantically secure. The quasi-dyadic McEliece variant proposed by Barreto and Misoczki addresses both problems. In this work we provide an implementation of this alternative public-key cryptosystem, which is semantically secure and uses a 40 times smaller public key and a five times smaller secret key compared to a previously published implementation [6].