A Key Recovery Reaction Attack on QCMDPC
(2019) In IEEE Transactions on Information Theory 65(3). p.18451861 Abstract
Algorithms for secure encryption in a postquantum world are currently receiving a lot of attention in the research community. One of the most promising such algorithms is the codebased scheme called QCMDPC, 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... (More)
Algorithms for secure encryption in a postquantum world are currently receiving a lot of attention in the research community. One of the most promising such algorithms is the codebased scheme called QCMDPC, 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 QCMDPC for 80bit security. It successfully recovers the secret key in minutes. A slightly modified version of the attack can be applied on proposed versions of the QCMDPC 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 80bit 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
 CCAsecurity, keyrecovery attack, postquantum cryptography, QCMDPC, reaction attack
 in
 IEEE Transactions on Information Theory
 volume
 65
 issue
 3
 pages
 17 pages
 publisher
 IEEEInstitute of Electrical and Electronics Engineers Inc.
 external identifiers

 scopus:85055167129
 ISSN
 00189448
 DOI
 10.1109/TIT.2018.2877458
 language
 English
 LU publication?
 yes
 id
 e629d3677a1a44ebb52da31f9f6e6ecc
 date added to LUP
 20181120 13:25:27
 date last changed
 20190314 11:05:18
@article{e629d3677a1a44ebb52da31f9f6e6ecc, abstract = {<p>Algorithms for secure encryption in a postquantum world are currently receiving a lot of attention in the research community. One of the most promising such algorithms is the codebased scheme called QCMDPC, 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 QCMDPC for 80bit security. It successfully recovers the secret key in minutes. A slightly modified version of the attack can be applied on proposed versions of the QCMDPC 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 80bit 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 = {00189448}, keyword = {CCAsecurity,keyrecovery attack,postquantum cryptography,QCMDPC,reaction attack}, language = {eng}, number = {3}, pages = {18451861}, publisher = {IEEEInstitute of Electrical and Electronics Engineers Inc.}, series = {IEEE Transactions on Information Theory}, title = {A Key Recovery Reaction Attack on QCMDPC}, url = {http://dx.doi.org/10.1109/TIT.2018.2877458}, volume = {65}, year = {2019}, }