A Key Recovery Reaction Attack on QC-MDPC
(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)
- author
- Guo, Qian LU ; Johansson, Thomas LU and Wagner, Paul Stankovski LU
- organization
- publishing date
- 2019
- 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
- 2023-09-08 12:02:28
@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&#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}}, keywords = {{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}}, doi = {{10.1109/TIT.2018.2877458}}, volume = {{65}}, year = {{2019}}, }