A reaction attack on the QCLDPC mceliece cryptosystem
(2017) 8th International Workshop on PostQuantum Cryptography, PQCrypto 2017 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10346 LNCS. p.5168 Abstract
Guo et al. recently presented a reaction attack against the QCMDPC McEliece cryptosystem. Their attack is based on the observation that when a bitflipping decoding algorithm is used in the QCMDPC McEliece, then there exists a dependence between the secret matrix H and the failure probability of the bitflipping algorithm. This dependence can be exploited to reveal the matrix H which constitutes the private key in the cryptosystem. It was conjectured that such dependence is present even when a softdecision decoding algorithm is used instead of a bitflipping algorithm. This paper shows that a similar dependence between the secret matrix H and the failure probability of a decoding algorithm is also present in the QCLDPC McEliece... (More)
Guo et al. recently presented a reaction attack against the QCMDPC McEliece cryptosystem. Their attack is based on the observation that when a bitflipping decoding algorithm is used in the QCMDPC McEliece, then there exists a dependence between the secret matrix H and the failure probability of the bitflipping algorithm. This dependence can be exploited to reveal the matrix H which constitutes the private key in the cryptosystem. It was conjectured that such dependence is present even when a softdecision decoding algorithm is used instead of a bitflipping algorithm. This paper shows that a similar dependence between the secret matrix H and the failure probability of a decoding algorithm is also present in the QCLDPC McEliece cryptosystem. Unlike QCMDPC McEliece, the secret key in QCLDPC McEliece also contains matrices S and Q in addition to the matrix H. We observe that there also exists a dependence between the failure probability and the matrix Q. We show that these dependences leak enough information to allow an attacker to construct a sparse paritycheck matrix for the public code. This paritycheck matrix can then be used for decrypting ciphertexts. We tested the attack on an implementation of the QCLDPC McEliece using a softdecision decoding algorithm. Thus we also confirmed that softdecision decoding algorithms can be vulnerable to leaking information about the secret key.
(Less)
 author
 Fabšič, Tomáš; Hromada, Viliam; Stankovski, Paul ^{LU} ; Zajac, Pavol; Guo, Qian ^{LU} and Johansson, Thomas ^{LU}
 organization
 publishing date
 2017
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 QCLDPC McEliece cryptosystem, Reaction attack, Softdecision decoding
 in
 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 volume
 10346 LNCS
 pages
 18 pages
 publisher
 Springer Verlag
 conference name
 8th International Workshop on PostQuantum Cryptography, PQCrypto 2017
 external identifiers

 scopus:85021776403
 ISSN
 03029743
 16113349
 ISBN
 9783319598789
 DOI
 10.1007/9783319598796_4
 language
 English
 LU publication?
 yes
 id
 e4ccbfe4d5ec4e0dac230ed0934226c5
 date added to LUP
 20170720 07:25:15
 date last changed
 20180107 12:12:19
@inproceedings{e4ccbfe4d5ec4e0dac230ed0934226c5, abstract = {<p>Guo et al. recently presented a reaction attack against the QCMDPC McEliece cryptosystem. Their attack is based on the observation that when a bitflipping decoding algorithm is used in the QCMDPC McEliece, then there exists a dependence between the secret matrix H and the failure probability of the bitflipping algorithm. This dependence can be exploited to reveal the matrix H which constitutes the private key in the cryptosystem. It was conjectured that such dependence is present even when a softdecision decoding algorithm is used instead of a bitflipping algorithm. This paper shows that a similar dependence between the secret matrix H and the failure probability of a decoding algorithm is also present in the QCLDPC McEliece cryptosystem. Unlike QCMDPC McEliece, the secret key in QCLDPC McEliece also contains matrices S and Q in addition to the matrix H. We observe that there also exists a dependence between the failure probability and the matrix Q. We show that these dependences leak enough information to allow an attacker to construct a sparse paritycheck matrix for the public code. This paritycheck matrix can then be used for decrypting ciphertexts. We tested the attack on an implementation of the QCLDPC McEliece using a softdecision decoding algorithm. Thus we also confirmed that softdecision decoding algorithms can be vulnerable to leaking information about the secret key.</p>}, author = {Fabšič, Tomáš and Hromada, Viliam and Stankovski, Paul and Zajac, Pavol and Guo, Qian and Johansson, Thomas}, booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}, isbn = {9783319598789}, issn = {03029743}, keyword = {QCLDPC McEliece cryptosystem,Reaction attack,Softdecision decoding}, language = {eng}, pages = {5168}, publisher = {Springer Verlag}, title = {A reaction attack on the QCLDPC mceliece cryptosystem}, url = {http://dx.doi.org/10.1007/9783319598796_4}, volume = {10346 LNCS}, year = {2017}, }