Advanced

A Key Recovery Reaction Attack on QC-MDPC

Guo, Qian LU ; Johansson, Thomas LU and Wagner, Paul Stankovski LU (2019) In IEEE Transactions on Information Theory 65(3). p.1845-1861
Abstract

Algorithms for secure encryption in a post-quantum world are currently receiving a lot of attention in the research community. One of the most promising such 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... (More)

Algorithms for secure encryption in a post-quantum world are currently receiving a lot of attention in the research community. One of the most promising such 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 INDCCA 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. Last, we present several algorithms for key reconstruction from an empirical distance spectrum. We first improve the naïve algorithm for key reconstruction by a factor of about 30,000, when the parameters for 80-bit security are implemented. We further develop the algorithm to deal with errors in the distance spectrum. This ultimately reduces the requirement on the number of ciphertexts that need to be collected for a successful key recovery.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
CCA-security, key-recovery attack, post-quantum cryptography, QC-MDPC, reaction attack
in
IEEE Transactions on Information Theory
volume
65
issue
3
pages
17 pages
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • scopus:85055167129
ISSN
0018-9448
DOI
10.1109/TIT.2018.2877458
language
English
LU publication?
yes
id
e629d367-7a1a-44eb-b52d-a31f9f6e6ecc
date added to LUP
2018-11-20 13:25:27
date last changed
2019-03-14 11:05:18
@article{e629d367-7a1a-44eb-b52d-a31f9f6e6ecc,
  abstract     = {<p>Algorithms for secure encryption in a post-quantum world are currently receiving a lot of attention in the research community. One of the most promising such 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 INDCCA 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. Last, we present several algorithms for key reconstruction from an empirical distance spectrum. We first improve the na&amp;#x00EF;ve algorithm for key reconstruction by a factor of about 30,000, when the parameters for 80-bit security are implemented. We further develop the algorithm to deal with errors in the distance spectrum. This ultimately reduces the requirement on the number of ciphertexts that need to be collected for a successful key recovery.</p>},
  author       = {Guo, Qian and Johansson, Thomas and Wagner, Paul Stankovski},
  issn         = {0018-9448},
  keyword      = {CCA-security,key-recovery attack,post-quantum cryptography,QC-MDPC,reaction attack},
  language     = {eng},
  number       = {3},
  pages        = {1845--1861},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  series       = {IEEE Transactions on Information Theory},
  title        = {A Key Recovery Reaction Attack on QC-MDPC},
  url          = {http://dx.doi.org/10.1109/TIT.2018.2877458},
  volume       = {65},
  year         = {2019},
}