A reaction attack on the QC-LDPC mceliece cryptosystem

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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.

Details

Authors
Organisations
External organisations
  • Slovak University of Technology in Bratislava
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science

Keywords

  • QC-LDPC McEliece cryptosystem, Reaction attack, Soft-decision decoding
Original languageEnglish
Title of host publicationPost-Quantum Cryptography - 8th International Workshop, PQCrypto 2017, Proceedings
PublisherSpringer Verlag
Pages51-68
Number of pages18
Volume10346 LNCS
ISBN (Print)9783319598789
StatePublished - 2017
Publication categoryResearch
Peer-reviewedYes
Event8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017 - Utrecht, Netherlands
Duration: 2017 Jun 262017 Jun 28

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10346 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017
CountryNetherlands
CityUtrecht
Period2017/06/262017/06/28