Solutions for the Storage Problem of McEliece Public and Private Keys on Memory-Constrained Platforms

摘要

While it is generally believed that due to their large public and private key sizes code based public key schemes like the McEliece PKC cannot be conveniently implemented on memory-constrained devices, we demonstrate otherwise. We show that for the public key we face rather a transmission problem than a storage problem: we propose an approach for Public Key Infrastructure (PKI) scenarios which totally eliminates the need to store public keys of communication partners. Instead, all the necessary computation steps are performed during the transmission of the key. We show the feasibility of the approach through an example implementation and give arguments that it will be possible for a smart card controller to carry out the associated computations fast enough to sustain the transmission rates of possible future high speed contactless interfaces. Concerning the McEliece private key, we demonstrate, contrasting to previously published implementations, that the parity check matrix, which is by far the largest part of this key, is not necessary to achieve fast decryption on embedded systems.