Two algorithms to improve the reaction attack on the QC-MDPC McEliece

• Thales Bandiera Paiva
• Routo Terada

Resumo

In 2016, a reaction attack on the QC-MDPC McEliece scheme was presented at Asiacrypt by Guo et al.. This attack exploits one aspect that was not considered in the scheme's security reduction: the probability of a decoding failure to occur is lower when the secret key and the error used for encryption share certain properties, which were called spectrums. By detecting decoding failures, the attacker can obtain information on the spectrum of the secret key and then use this information to reconstruct the key. To improve the efficiency of the attack, we propose two different key reconstruction algorithms that are more efficient and use less information on the secret key than Guo's et al. one. Furthermore, both algorithms can be trivially parallelized.