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

Qian Guo; Thomas Johansson; Paul Stankovski

doi:10.1007/978-3-662-53887-6_29

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

Qian Guo, Thomas Johansson, Paul Stankovski

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

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

Original language	English
Title of host publication	Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Publisher	Springer
Pages	789-815
Number of pages	27
Volume	10031 LNCS
ISBN (Print)	9783662538869
DOIs	https://doi.org/10.1007/978-3-662-53887-6_29
Publication status	Published - 2016
Event	22nd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2016 - Hanoi, Viet Nam Duration: 2016 Dec 4 → 2016 Dec 8

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10031 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	22nd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2016
Country/Territory	Viet Nam
City	Hanoi
Period	2016/12/04 → 2016/12/08

Subject classification (UKÄ)

Computer Science

Free keywords

CCA-security
Key-recovery attack
Post-quantum cryptography
QC-MDPC
Reaction attack

Access to Document

10.1007/978-3-662-53887-6_29

Cite this

Guo, Q., Johansson, T., & Stankovski, P. (2016). A key recovery attack on MDPC with CCA security using decoding errors. In Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (Vol. 10031 LNCS, pp. 789-815). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10031 LNCS). Springer. https://doi.org/10.1007/978-3-662-53887-6_29

Guo, Qian ; Johansson, Thomas ; Stankovski, Paul. / A key recovery attack on MDPC with CCA security using decoding errors. Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Vol. 10031 LNCS Springer, 2016. pp. 789-815 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{88d7505ffb444268999e2f6f61a0429d,

title = "A key recovery attack on MDPC with CCA security using decoding errors",

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 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.",

keywords = "CCA-security, Key-recovery attack, Post-quantum cryptography, QC-MDPC, Reaction attack",

author = "Qian Guo and Thomas Johansson and Paul Stankovski",

year = "2016",

doi = "10.1007/978-3-662-53887-6_29",

language = "English",

isbn = "9783662538869",

volume = "10031 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "789--815",

booktitle = "Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "Germany",

note = "22nd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2016 ; Conference date: 04-12-2016 Through 08-12-2016",

}

Guo, Q , Johansson, T & Stankovski, P 2016, A key recovery attack on MDPC with CCA security using decoding errors. in Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. vol. 10031 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10031 LNCS, Springer, pp. 789-815, 22nd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2016, Hanoi, Viet Nam, 2016/12/04. https://doi.org/10.1007/978-3-662-53887-6_29

A key recovery attack on MDPC with CCA security using decoding errors. / Guo, Qian ; Johansson, Thomas ; Stankovski, Paul.
Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Vol. 10031 LNCS Springer, 2016. p. 789-815 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10031 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

TY - GEN

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

AU - Guo, Qian

AU - Johansson, Thomas

AU - Stankovski, Paul

PY - 2016

Y1 - 2016

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

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

KW - CCA-security

KW - Key-recovery attack

KW - Post-quantum cryptography

KW - QC-MDPC

KW - Reaction attack

UR - http://www.scopus.com/inward/record.url?scp=84998705796&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-53887-6_29

DO - 10.1007/978-3-662-53887-6_29

M3 - Paper in conference proceeding

AN - SCOPUS:84998705796

SN - 9783662538869

VL - 10031 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 789

EP - 815

BT - Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

PB - Springer

T2 - 22nd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT), 2016

Y2 - 4 December 2016 through 8 December 2016

ER -

Guo Q , Johansson T , Stankovski P. A key recovery attack on MDPC with CCA security using decoding errors. In Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Vol. 10031 LNCS. Springer. 2016. p. 789-815. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-53887-6_29

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

Abstract

Publication series

Conference

Subject classification (UKÄ)

Free keywords

Access to Document

Other files and links

Fingerprint

Using Coding Techniques for Attacking Post-Quantum Cryptographic Assumptions and Systems

Cite this