Improving the Efficiency of a Reaction Attack on the QC-MDPC McEliece

Autor(es)

Bandiera Paiva, Thales ^[1] ; Terada, Routo ^[1]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Dept Comp Sci, Sao Paulo, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES; v. E101A, n. 10, p. 1676-1686, OCT 2018.
• Citações Web of Science: 0

Resumo

The QC-MDPC McEliece scheme was considered one of the most promising public key encryption schemes for efficient post-quantum secure encryption. As a variant of the McEliece scheme, it is based on the syndrome decoding problem, which is a hard problem from Coding Theory. Its key sizes are competitive with the ones of the widely used RSA cryptosystem, and it came with an apparently strong security reduction. For three years, the scheme has not suffered major threats, until the end of 2016, at the Asiacrypt, when Guo, Johansson, and Stankovski presented a reaction attack on the QC-MDPC that exploits one aspect that was not considered in the 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. Recording the decoding failures, the attacker obtains information about the secret key and then use the information gathered to reconstruct the key. Guo et al. presented an algorithm for key reconstruction for which we can point two weaknesses. The first one is that it cannot deal with partial information about the secret key, resulting in the attacker having to send a large number of decoding challenges. The second one is that it does not scale well for higher security levels. To improve the attack, we propose a key reconstruction algorithm that runs faster than Guo's et al. algorithm, even using around 20% less interactions with the secret key holder than used by their algorithm, considering parameters suggested for 80 bits of security. It also has a lower asymptotic complexity which makes it scale much better for higher security parameters. The algorithm can be parallelized straightforwardly, which is not the case for the one by Guo et al. (AU)

• Processo FAPESP: 15/01587-0 - Armazenagem, modelagem e análise de sistemas dinâmicos para aplicações em e-Science
• Beneficiário: João Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Programa eScience e Data Science - Temático