Cryptology ePrint Archive: Report 2018/140

A Reaction Attack on LEDApkc

Tomas Fabsic and 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$.

Category / Keywords: public-key cryptography / LEDApkc, QC-LDPC McEliece cryptosystem, reaction attack, post-quantum cryptography

Date: received 6 Feb 2018

Contact author: tomas fabsic at stuba sk

Available format(s): PDF | BibTeX Citation

Version: 20180207:180607 (All versions of this report)

Short URL: ia.cr/2018/140

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]