Advanced

A key recovery attack on MDPC with CCA security using decoding errors

Guo, Qian LU ; Johansson, Thomas LU and Stankovski, Paul LU (2016) 22nd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2016 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10031 LNCS. p.789-815
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 QCMDPC 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... (More)

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 QCMDPC 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.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
CCA-security, Key-recovery attack, Post-quantum cryptography, QC-MDPC, Reaction attack
in
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
volume
10031 LNCS
pages
27 pages
publisher
Springer Verlag
conference name
22nd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2016
external identifiers
  • scopus:84998705796
  • scopus:84998705796
  • wos:000389692500029
ISSN
03029743
16113349
ISBN
9783662538869
DOI
10.1007/978-3-662-53887-6_29
language
English
LU publication?
yes
id
88d7505f-fb44-4268-999e-2f6f61a0429d
date added to LUP
2016-09-08 11:31:15
date last changed
2017-09-24 05:00:33
@inproceedings{88d7505f-fb44-4268-999e-2f6f61a0429d,
  abstract     = {<p>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 QCMDPC 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.</p>},
  author       = {Guo, Qian and Johansson, Thomas and Stankovski, Paul},
  booktitle    = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
  isbn         = {9783662538869},
  issn         = {03029743},
  keyword      = {CCA-security,Key-recovery attack,Post-quantum cryptography,QC-MDPC,Reaction attack},
  language     = {eng},
  pages        = {789--815},
  publisher    = {Springer Verlag},
  title        = {A key recovery attack on MDPC with CCA security using decoding errors},
  url          = {http://dx.doi.org/10.1007/978-3-662-53887-6_29},
  volume       = {10031 LNCS},
  year         = {2016},
}