QC-MDPC: A Timing Attack and a CCA2 KEM

Edward Eaton; Matthieu Lequesne; Alex Parent; Nicolas Sendrier

Paper 2018/256

QC-MDPC: A Timing Attack and a CCA2 KEM

Edward Eaton, Matthieu Lequesne, Alex Parent, and Nicolas Sendrier

Abstract

In 2013, Misoczki, Tillich, Sendrier and Barreto proposed a variant of the McEliece cryptosystem based on quasi-cyclic moderate-density parity-check (QC-MDPC) codes. This proposal uses an iterative bit-flipping algorithm in its decryption procedure. Such algorithms fail with a small probability. At Asiacrypt 2016, Guo, Johansson and Stankovski (GJS) exploited these failures to perform a key recovery attack. They introduced the notion of the distance spectrum of a sparse vector and showed that the knowledge of the spectrum is enough to find the vector. By observing many failing plaintexts they recovered the distance spectrum of the QC-MDPC secret key. In this work, we explore the underlying causes of this attack, ways in which it can be improved, and how it can be mitigated. We prove that correlations between the spectrum of the key and the spectrum of the error induce a bias on the distribution of the syndrome weight. Hence, the syndrome weight is the fundamental quantity from which secret information leaks. Assuming a side-channel allows the observation of the syndrome weight, we are able to perform a key-recovery attack, which has the advantage of exploiting all known plaintexts, not only those leading to a decryption failure. Based on this study, we derive a timing attack. It performs well on most decoding algorithms, even on the recent variants where the decryption failure rate is low, a case which is more challenging to the GJS attack. To our knowledge, this is the first timing attack on a QC-MDPC scheme. Finally, we show how to construct a new KEM, called ParQ that can reduce the decryption failure rate to a level negligible in the security parameter, without altering the QC-MDPC parameters. This is done through repeated encryption. We formally prove the IND-CCA2 security of ParQ, in a model that considers decoding failures. This KEM offers smaller key sizes and is suitable for purposes where the public key is used statically.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. PQCrypto 2018; The Ninth International Conference on Post-Quantum Cryptography
Keywords: post-quantum cryptography code-based cryptography QC-MDPC codes side-channel attack timing attack CCA2 security key encapsulation
Contact author(s): ted eaton @ isara com
History: 2018-03-09: received
Short URL: https://ia.cr/2018/256
License: CC BY

BibTeX

@misc{cryptoeprint:2018/256,
      author = {Edward Eaton and Matthieu Lequesne and Alex Parent and Nicolas Sendrier},
      title = {{QC}-{MDPC}: A Timing Attack and a {CCA2} {KEM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/256},
      year = {2018},
      url = {https://eprint.iacr.org/2018/256}
}