Paper 2015/425

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

Stefan Heyse, 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in CHES 2013
DOI
10.1007/978-3-642-40349-1_16
Keywords
public key cryptographycode-basedMcElieceMDPCFPGAmicrocontroller
Contact author(s)
ingo vonmaurich @ rub de
History
2015-05-05: received
Short URL
https://ia.cr/2015/425
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/425,
      author = {Stefan Heyse and Ingo von Maurich and Tim Güneysu},
      title = {Smaller Keys for Code-Based Cryptography: QC-MDPC McEliece Implementations on Embedded Devices},
      howpublished = {Cryptology ePrint Archive, Paper 2015/425},
      year = {2015},
      doi = {10.1007/978-3-642-40349-1_16},
      note = {\url{https://eprint.iacr.org/2015/425}},
      url = {https://eprint.iacr.org/2015/425}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.