2024/10/14 by Gretchen L. Matthews, Matthews, Gretchen L, Emily McMillon +1
Computer Science · #81P94 #94A60 (Primary) #94B05 #94B35 (Secondary) #Chaos-based Image/Signal Encryption #Coding theory and cryptography #Cryptographic Implementations and Security #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2410.11111
openalex publication_date 2024/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Bit Flipping Key Encapsulation (BIKE) is a code-based cryptosystem that was considered in Round 4 of the NIST Post-Quantum Cryptography Standardization process. It is based on quasi-cyclic moderate-density parity-check (QC-MDPC) codes paired with an iterative decoder. While (low-density) parity-check codes have been shown to perform well in practice, their capabilities are governed by the code's graphical representation and the choice of decoder rather than the traditional code parameters, making it difficult to determine the decoder failure rate (DFR). Moreover, decoding failures have been demonstrated to lead to attacks that recover the BIKE private key. In this paper, we demonstrate a strong correlation between weak keys and 4-cycles in their associated Tanner graphs. We give concrete ways to enumerate the number of 4-cycles in a BIKE key and use these results to present a filtering algorithm that will filter BIKE keys with large numbers of 4-cycles. These results also apply to more general parity check codes.