Advanced

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 Post-Quantum Cryptography - 8th International Workshop, PQCrypto 2017, Proceedings 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)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
QC-LDPC McEliece cryptosystem, Reaction attack, Soft-decision decoding
in
Post-Quantum Cryptography - 8th International Workshop, PQCrypto 2017, Proceedings
volume
10346 LNCS
pages
18 pages
publisher
Springer Verlag
conference name
8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017
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
2018-05-06 04:35:28
@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},
  keyword      = {QC-LDPC McEliece cryptosystem,Reaction attack,Soft-decision decoding},
  language     = {eng},
  pages        = {51--68},
  publisher    = {Springer Verlag},
  title        = {A reaction attack on the QC-LDPC mceliece cryptosystem},
  url          = {http://dx.doi.org/10.1007/978-3-319-59879-6_4},
  volume       = {10346 LNCS},
  year         = {2017},
}