A reaction attack on the QC-LDPC mceliece cryptosystem

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding


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.


Enheter & grupper
Externa organisationer
  • Slovak University of Technology in Bratislava

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)


Titel på värdpublikationPost-Quantum Cryptography - 8th International Workshop, PQCrypto 2017, Proceedings
Antal sidor18
Volym10346 LNCS
ISBN (tryckt)9783319598789
StatusPublished - 2017
Peer review utfördJa
Evenemang8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017 - Utrecht, Nederländerna
Varaktighet: 2017 jun 262017 jun 28


NamnLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volym10346 LNCS
ISSN (tryckt)03029743
ISSN (elektroniskt)16113349


Konferens8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017