A Novel code-based public-key encryption using semi-MDPC codes

Abstract BIKE is a post-quantum public-key encryption scheme based on Moderate-Density Parity-Check (MDPC) codes, gaining significant attention for its small public key and ciphertext sizes. However, it suffers from several critical limitations, including the lack of precise theoretical bounds for estimating the Decryption Failure Rate (DFR) and its vulnerability to weak-key and near-codeword attacks. These shortcomings ultimately contributed to its failure to be selected for standardization. To address these challenges, we propose an enhanced variant of the BIKE cryptosystem based on semi-MDPC codes. We reduce the syndrome decoding problem for semi-MDPC codes to the Quasi-Cyclic Codeword Finding and Quasi-Cyclic Syndrome Decoding problems. The proposed scheme resists major attacks specific to BIKE, such as weak-key and near-codeword attacks, while also enabling a rigorous theoretical analysis of the DFR with provable upper bounds–significantly improving security and reliability. Furthermore, we introduce a block-cyclic matrix structure to enhance security and reduce ciphertext size at the cost of an increased public key size. Compared with McEliece, our scheme achieves significantly smaller key sizes. Against the standardized HQC scheme, while the public key is approximately twice as large, the ciphertext size is reduced by about 50%, offering superior storage efficiency in ciphertext-constrained environments.