A reaction attack on the QC-LDPC mceliece cryptosystem
Fabšič, Tomáš ; Hromada, Viliam ; Stankovski, Paul LU ; Zajac, Pavol ; Guo, Qian LU and Johansson, Thomas LU
(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
- 16113349
- 03029743
- 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-04-14 14:27:43
@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 = {{16113349}},
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}},
}