Cryptology ePrint Archive: Report 2012/409

MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes

Rafael Misoczki and Jean-Pierre Tillich and Nicolas Sendrier and Paulo S. L. M. Barreto

Abstract: In this work, we propose two McEliece variants. One from Moderate Density Parity-Check (MDPC) codes and other from quasi-cyclic MDPC codes. MDPC codes are LDPC codes of higher density than what is usually adopted for telecommunication applications, providing an worse error-correction capability. However, in cryptography, we are not necessarily interested in correcting many errors, but only a number which ensures an adequate security level, a condition satisfied by MDPC codes. The benefits of their employment are many. Under a reasonable assumption, MDPC codes reduce the key-distinguishing McEliece problem to the problem of decoding a linear code. This leads the security of our variant to rely only on a single, well studied coding-theory problem. Furthermore, in the quasi-cyclic case, our proposal provides extremely compact-keys (for $80$-bits of security, public-keys have only $4800$ bits).

Category / Keywords: post-quantum cryptography, code-based cryptography, coding-theory, LDPC codes

Date: received 23 Jul 2012, last revised 5 Feb 2013

Contact author: rafael misoczki at inria fr

Available formats: PDF | BibTeX Citation

Version: 20130205:225105 (All versions of this report)

Discussion forum: Show discussion | Start new discussion