Code-based cryptosystems are among the leading candidates for post-quantum cryptography. In NIST's standardization process, a lattice-based scheme was selected as the primary standard for key encapsulation, while the code-based HQC (Hamming Quasi-Cyclic)was chosen as a backup. Code-based approaches are also gaining attention in European postquantum standardization efforts. Among code-based schemes, the McEliece cryptosystem is one of the oldest and most extensively studied. In particular, its QC-MDPC (quasi-cyclic moderate-density parity-check) variant, which underlies the BIKE (Bit Flipping Key Encapsulation) scheme, a Round-4 candidate in NIST's standardization process, is noteworthy due to its small key length. The Guo-Johansson-Stankovski (GJS) attack against the QC-MDPC McEliece cryptosystem was proposed in 2016 and has intensively been studied. This attack reconstructs the secret key using information on decoding error rate (DER). However, in practice, obtaining complete DER information is presumed to be time-consuming. Although this imperfection has been discussed since the attack was originally proposed, explicit algorithms that work under the imperfection have been less studied. This paper proposes two algorithms to reconstruct the secret key under imperfection in the DER information by simply modifying previously known algorithms that work with complete DER information. We evaluate the relationship between the imperfection and efficiency of key reconstruction. This will help us to increase the efficacy of the GJS attack.
Ohtsuka et al. (Thu,) studied this question.