Two algorithms to improve the reaction attack on the QC-MDPC McEliece
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.
Referências
Augot, D., Batina, L., Bernstein, D. J., Bos, J., Buchmann, J., Castryck, W., Dunkelman, O., Güneysu, T., Gueron, S., and Hülsing, A. (2015). Initial recommendations of long-term secure post-quantum systems.
Bernstein, D. J., Chou, T., and Schwabe, P. (2013). McBits: fast constant-time code-based cryptography. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 250–272. Springer.
Fabšič, T., Hromada, V., Stankovski, P., Zajac, P., Guo, Q., and Johansson, T. (2017). A reaction attack on the QC-LDPC McEliece cryptosystem. In International Workshop on Post-Quantum Cryptography, pages 51–68. Springer.
Gallager, R. (1962). Low-density parity-check codes. IRE Transactions on information theory, 8(1):21–28.
Guo, Q., Johansson, T., and Stankovski, P. (2016). A key recovery attack on MDPC with CCA security using decoding errors. In 22nd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT).
Misoczki, R., Tillich, J. P., Sendrier, N., and Barreto, P. S. L. M. (2013). MDPC-McEliece: New McEliece variants from moderate density parity-check codes. In IEEE International Symposium on Information Theory, pages 2069–2073. IEEE.
Paiva, T. B. and Terada, R. (2018). Improving the efficiency of a reaction attack on the QC-MDPC McEliece (to appear in 2018). IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences.
