Cryptography Reference
In-Depth Information
Implementation of McEliece
Based on Quasi-dyadic Goppa Codes
for Embedded Devices
Stefan Heyse
Horst Gortz Institute for IT Security
Ruhr University Bochum
44780 Bochum, Germany
heyse@crypto.rub.de
Abstract.
Most public-key cryptosystems frequently implemented have
been proven secure on the basis of the presumed hardness of two math-
ematical 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 computa-
tions 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 eciently. Furthermore, the imple-
mentations have to perform fast while keeping memory requirements low
for security levels comparable to conventional schemes. The McEliece en-
cryption and decryption do not require computationally expensive mul-
tiple 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 alter-
native 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].
Keywords:
McEliece, Goppa Code, Quasi-Dyadic, Embedded Device,
Post-Quantum.
1
Introduction
Only few implementations of the original McEliece public-key cryptosystem have
been reported. For instance, there exist two software implementations for 32-bit
