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 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)
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
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 Post-Quantum Cryptography, PQCrypto 2017
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
2017-07-20 07:25:15
@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    = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
  isbn         = {9783319598789},
  issn         = {03029743},
  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},
}