Paper 2018/140

A Reaction Attack on LEDApkc

Tomas Fabsic, Viliam Hromada, and Pavol Zajac

Abstract

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
LEDApkcQC-LDPC McEliece cryptosystemreaction attackpost-quantum cryptography
Contact author(s)
tomas fabsic @ stuba sk
History
2018-02-07: received
Short URL
https://ia.cr/2018/140
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/140,
      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{https://eprint.iacr.org/2018/140}},
      url = {https://eprint.iacr.org/2018/140}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.