An Optimization of Weak Key Attacks Based on the BGF Decoding Algorithm

Among the four candidate algorithms in the fourth round of NIST standardization, the BIKE (Bit Flipping Key Encapsulation) scheme has a small key size and high efficiency, showing good prospects for application. However, the BIKE scheme based on QC-MDPC (Quasi Cyclic Medium Density Parity Check) codes still faces challenges such as the GJS attack and weak key attacks targeting the decoding failure rate (DFR). This paper analyzes the BGF decoding algorithm of the BIKE scheme, revealing two deep factors that lead to DFR, and proposes a weak key optimization attack method for the BGF decoding algorithm based on these two factors. The proposed method constructs a new weak key set, and experiment results eventually indicate that, considering BIKE’s parameter set targeting 128-bit security, the average decryption failure rate is lowerly bounded by . This result not only highlights a significant vulnerability in the BIKE scheme but also provides valuable insights for future improvements in its design. By addressing these weaknesses, the robustness of QC-MDPC code-based cryptographic systems can be enhanced, paving the way for more secure post-quantum cryptographic solutions.