Paper 2018/140

A Reaction Attack on LEDApkc

Tomas Fabsic, Viliam Hromada, and Pavol Zajac


We propose a new reaction attack on the public-key cryptosystem LEDApkc. The adversary uses the decoding failure rate (DFR) analysis to learn information about the secret masking matrix $Q$. Provided the adversary learns information about $Q$ within $10^4\times \text{DFR}^{-1}$ decryptions (as prescribed by LEDApkc design to thwart previously known attacks), the adversary builds a small set of candidates for $Q$. Using these candidates, the adversary obtains candidates for a generator matrix of the secret LDPC code. Afterwards, the adversary applies Stern's algorithm to recover the secret matrix $H$, thus recovering the full private key. Provided the adversary can learn information about the matrix $Q$, the complexity of the attack is below $2^{99}$ for a parameter set for 128-bit security. In order to study whether the adversary can learn information about $Q$ from $10^4\times \text{DFR}^{-1}$ decryptions, we conducted experiments with a modified parameter set. The parameter set was modified only in order to increase the DFR, and thus make experiments less computationally expensive. We show that with the modified parameter set it is indeed possible to learn the required information about the matrix $Q$.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
LEDApkcQC-LDPC McEliece cryptosystemreaction attackpost-quantum cryptography
Contact author(s)
tomas fabsic @ stuba sk
2018-02-07: received
Short URL
Creative Commons Attribution


      author = {Tomas Fabsic and Viliam Hromada and Pavol Zajac},
      title = {A Reaction Attack on LEDApkc},
      howpublished = {Cryptology ePrint Archive, Paper 2018/140},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.