Paper 2016/858

A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors

Qian Guo, Thomas Johansson, and Paul Stankovski

Abstract

Algorithms for secure encryption in a post-quantum world are currently receiving a lot of attention in the research community, including several larger projects and a standardization effort from NIST. One of the most promising algorithms is the code-based scheme called QC-MDPC, which has excellent performance and a small public key size. In this work we present a very efficient key recovery attack on the QC-MDPC scheme using the fact that decryption uses an iterative decoding step and this can fail with some small probability. We identify a dependence between the secret key and the failure in decoding. This can be used to build what we refer to as a distance spectrum for the secret key, which is the set of all distances between any two ones in the secret key. In a reconstruction step we then determine the secret key from the distance spectrum. The attack has been implemented and tested on a proposed instance of QC-MDPC for 80 bit security. It successfully recovers the secret key in minutes. A slightly modified version of the attack can be applied on proposed versions of the QC-MDPC scheme that provides IND-CCA security. The attack is a bit more complex in this case, but still very much below the security level. The reason why we can break schemes with proved CCA security is that the model for these proofs typically does not include the decoding error possibility.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2016
Keywords
CCA-securitykey-recovery attackpost-quantum cryptographyQC-MDPCreaction attack.
Contact author(s)
qian guo @ eit lth se
thomas johansson @ eit lth se
paul stankovski @ eit lth se
fywzguoqian @ gmail com
History
2016-09-08: received
Short URL
https://ia.cr/2016/858
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/858,
      author = {Qian Guo and Thomas Johansson and Paul Stankovski},
      title = {A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2016/858},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/858}},
      url = {https://eprint.iacr.org/2016/858}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.