Cryptology ePrint Archive: Report 2015/425

Smaller Keys for Code-Based Cryptography: QC-MDPC McEliece Implementations on Embedded Devices

Stefan Heyse and Ingo von Maurich and Tim GŁneysu

Abstract: In the last years code-based cryptosystems were established as promising alternatives for asymmetric cryptography since they base their security on well-known NP-hard problems and still show decent performance on a wide range of computing platforms. The main drawback of code-based schemes, including the popular proposals by McEliece and Niederreiter, are the large keys whose size is inherently determined by the underlying code. In a very recent approach, Misoczki et al. proposed to use quasi-cyclic MDPC (QC-MDPC) codes that allow for a very compact key representation. In this work, we investigate novel implementations of the McEliece scheme using such QC-MDPC codes tailored for embedded devices, namely a Xilinx Virtex-6 FPGA and an 8-bit AVR microcontroller. In particular, we evaluate and improve different approaches to decode QC-MDPC codes. Besides competitive performance for encryption and decryption on the FPGA, we achieved a very compact implementation on the microcontroller using only 4,800 and 9,600 bits for the public and secret key at 80 bits of equivalent symmetric security.

Category / Keywords: implementation / public key cryptography, code-based, McEliece, MDPC, FPGA, microcontroller

Original Publication (in the same form): IACR-CHES-2013

Date: received 4 May 2015

Contact author: ingo vonmaurich at rub de

Available format(s): PDF | BibTeX Citation

Version: 20150505:192323 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]