Paper 2012/409

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

Rafael Misoczki, Jean-Pierre Tillich, 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.

Note: To be in accordance with the submitted version (ISIT).

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Short version to appear at ISIT 2013. IEEE International Symposium on Information Theory. July 7-12, 2013 -- Istanbul, Turkey.
Keywords
post-quantum cryptographycode-based cryptographycoding-theoryLDPC codes
Contact author(s)
rafael misoczki @ inria fr
History
2013-05-30: last of 3 revisions
2012-07-25: received
See all versions
Short URL
https://ia.cr/2012/409
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/409,
      author = {Rafael Misoczki and Jean-Pierre Tillich and Nicolas Sendrier and Paulo S.  L.  M.  Barreto},
      title = {{MDPC}-{McEliece}: New {McEliece} Variants from Moderate Density Parity-Check Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2012/409},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/409}},
      url = {https://eprint.iacr.org/2012/409}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.