Efficient Reconstruction in Key Recovery Attack on the QC-MDPC McEliece Cryptosystems

Realization of large quantum computers is believed to jeopardize the security of cryptosystems relying on computational complexity of some mathematical problems, such as prime factorization and discrete logarithm problem. In this light, post-quantum cryptography, which is secure even after large quantum computers are realized, has been getting a lot of attention. National Institute of Standards and Technology (NIST) recently started a standardization process for post-quantum cryptosystems. The McEliece public-key cryptosystem based on quasi-cyclic moderate-density parity-check (QC-MDPC) codes is a promising candidate in this NIST standardization. Recently, attacks on the QC-MDPC McEliece scheme have extensively been investigated. The one proposed by Guo et al. exploits statistical information of decoding errors to reconstruct the secret key. This attack is twofold: (1) obtaining the distance spectrum of the secret key from statistical information of decoding errors, and (2) reconstructing the secret key from the distance spectrum. The bit-flipping decoding, which is commonly used to decode the QC-MDPC scheme, is considered to be vulnerable to the first part of this attack. Meanwhile the second part of the attack in the original version by Guo et al. requires considerable time because they use recursive search in this part. In this paper, we propose another method to reconstruct the secret key from the obtained distance spectrum on the basis of a method proposed by Fabšič et al. They found that the key construction can be mapped to a clique problem in graph theory. Using their observation, we apply a breadth-first search algorithm to the key reconstruction. Numerical experiments show that our method reconstructs the secret key more efficiently than recursive search in the original key reconstruction proposed by Guo et al.