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 cryptosystem variants: one from Moderate Density Parity-Check (MDPC) codes and another from quasi-cyclic MDPC codes. MDPC codes are LDPC codes of higher density than what is usually adopted for telecommunication applications. In general, this leads to a worse error-correction capability. However, in code-based 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 linear codes. Since the message-attacks against the McEliece scheme also reduce to this problem, the security of our scheme has the benefit of relying on a single, well studied coding-theory problem. Furthermore, adding a quasi-cyclic structure, our proposal provides extremely compact-keys: for $80$-bits of security, the public-key has only $4801$ bits.
Category / Keywords: post-quantum cryptography, code-based cryptography, coding-theory, LDPC codes
Publication Info: Short version to appear at ISIT 2013. IEEE International Symposium on Information Theory. July 7-12, 2013 -- Istanbul, Turkey.
Date: received 23 Jul 2012, last revised 30 May 2013
Contact author: rafael misoczki at inria fr
Available formats: PDF | BibTeX Citation
Note: To be in accordance with the submitted version (ISIT).
Version: 20130530:121403 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]