Paper 2017/494

A Reaction Attack on the QC-LDPC McEliece Cryptosystem

Tomas Fabsic, Viliam Hromada, Paul Stankovski, Pavol Zajac, Qian Guo, and Thomas Johansson

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 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. PQCrypto 2017
Keywords
QC-LDPC McEliece cryptosystemreaction attacksoft-decision decoding
Contact author(s)
tomas fabsic @ stuba sk
History
2017-06-01: received
Short URL
https://ia.cr/2017/494
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/494,
      author = {Tomas Fabsic and Viliam Hromada and Paul Stankovski and Pavol Zajac and Qian Guo and Thomas Johansson},
      title = {A Reaction Attack on the {QC}-{LDPC} {McEliece} Cryptosystem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/494},
      year = {2017},
      url = {https://eprint.iacr.org/2017/494}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.