A combinatorial approach to avoiding weak keys in the BIKE cryptosystem

The article delves into the critical issue of weak keys in the BIKE cryptosystem, a post-quantum cryptographic system designed to withstand attacks aided by quantum computers. It begins by discussing the historical context and the necessity of post-quantum cryptography, highlighting the vulnerabilities of traditional systems like RSA and Diffie–Hellman. The focus then shifts to the BIKE cryptosystem, which utilizes quasi-cyclic moderate-density parity-check (QC-MDPC) codes to achieve compact representations and efficient decoding. The core of the article introduces a combinatorial approach to identify and avoid weak keys, which are known to cause decoding failures. By enumerating 4-cycles in the underlying graph of the private key, the authors provide a new filter to enhance the security of the BIKE cryptosystem. Experimental results demonstrate the utility of this approach, showing that 4-cycles within a single circulant block are more conducive to weak keys than those across blocks. The article also extends these findings to general QC-MDPC codes, offering a broader perspective on the impact of short cycles in iterative decoding. The detailed analysis and experimental data presented make this article a valuable resource for understanding and mitigating decoding failures in post-quantum cryptographic systems.