A reaction attack on the QC-LDPC mceliece cryptosystem
(2017) 8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10346 LNCS. p.51-68- Abstract
Guo et al. recently presented a reaction attack against the QC-MDPC McEliece cryptosystem. Their attack is based on the observation that when a bit-flipping decoding algorithm is used in the QC-MDPC McEliece, then there exists a dependence between the secret matrix H and the failure probability of the bit-flipping 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 soft-decision decoding algorithm is used instead of a bit-flipping 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 QC-LDPC McEliece... (More)
Guo et al. recently presented a reaction attack against the QC-MDPC McEliece cryptosystem. Their attack is based on the observation that when a bit-flipping decoding algorithm is used in the QC-MDPC McEliece, then there exists a dependence between the secret matrix H and the failure probability of the bit-flipping 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 soft-decision decoding algorithm is used instead of a bit-flipping 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 QC-LDPC McEliece cryptosystem. Unlike QC-MDPC McEliece, the secret key in QC-LDPC 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 parity-check matrix for the public code. This parity-check matrix can then be used for decrypting ciphertexts. We tested the attack on an implementation of the QC-LDPC McEliece using a soft-decision decoding algorithm. Thus we also confirmed that soft-decision 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
- QC-LDPC McEliece cryptosystem, Reaction attack, Soft-decision decoding
- host publication
- Post-Quantum Cryptography - 8th International Workshop, PQCrypto 2017, Proceedings
- series title
- 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
- conference name
- 8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017
- conference location
- Utrecht, Netherlands
- conference dates
- 2017-06-26 - 2017-06-28
- external identifiers
-
- scopus:85021776403
- ISSN
- 03029743
- 16113349
- ISBN
- 9783319598789
- DOI
- 10.1007/978-3-319-59879-6_4
- language
- English
- LU publication?
- yes
- id
- e4ccbfe4-d5ec-4e0d-ac23-0ed0934226c5
- date added to LUP
- 2017-07-20 07:25:15
- date last changed
- 2024-09-16 05:16:35
@inproceedings{e4ccbfe4-d5ec-4e0d-ac23-0ed0934226c5, abstract = {{<p>Guo et al. recently presented a reaction attack against the QC-MDPC McEliece cryptosystem. Their attack is based on the observation that when a bit-flipping decoding algorithm is used in the QC-MDPC McEliece, then there exists a dependence between the secret matrix H and the failure probability of the bit-flipping 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 soft-decision decoding algorithm is used instead of a bit-flipping 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 QC-LDPC McEliece cryptosystem. Unlike QC-MDPC McEliece, the secret key in QC-LDPC 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 parity-check matrix for the public code. This parity-check matrix can then be used for decrypting ciphertexts. We tested the attack on an implementation of the QC-LDPC McEliece using a soft-decision decoding algorithm. Thus we also confirmed that soft-decision 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 = {{Post-Quantum Cryptography - 8th International Workshop, PQCrypto 2017, Proceedings}}, isbn = {{9783319598789}}, issn = {{03029743}}, keywords = {{QC-LDPC McEliece cryptosystem; Reaction attack; Soft-decision decoding}}, language = {{eng}}, pages = {{51--68}}, publisher = {{Springer}}, series = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}}, title = {{A reaction attack on the QC-LDPC mceliece cryptosystem}}, url = {{http://dx.doi.org/10.1007/978-3-319-59879-6_4}}, doi = {{10.1007/978-3-319-59879-6_4}}, volume = {{10346 LNCS}}, year = {{2017}}, }