Implementing QC-MDPC McEliece Encryption

Ingo von Maurich, Tobias Oder, Tim Güneysu

ACM Transactions on Embedded Computing Systems (TECS) - Special Issue on Embedded Platforms for Crypto and Regular Papers TECS, Volume 14 Issue 3, May 2015, Article No. 44, ACM New York, NY, USA.


With respect to performance, asymmetric code-based cryptography based on binary Goppa codes has been reported as a highly interesting alternative to RSA and ECC. A major drawback are still the large keys in the range between 50-100 kByte that prevented real-world applications of code-based cryptosystems so far. A recent proposal by Misoczki et al. showed that quasi-cyclic moderate-density parity-check (QC-MDPC) codes can be used in McEliece encryption -- reducing the public key to just 0.6 kByte to achieve an 80-bit security level. In this article we provide optimized decoding techniques for MDPC codes and survey several efficient implementations of the QC-MDPC McEliece cryptosystem. This includes high-speed and lightweight architectures for reconfigurable hardware, efficient coding styles for ARM's Cortex-M4 microcontroller but also novel high-performance software implementations that fully employ vector instructions. Finally, we conclude that McEliece encryption in combination with QC-MDPC codes not only enables high-performance implementations but also allows for lightweight designs on a wide range of different platforms.