A Combinatorial Approach to Avoiding Weak Keys in the BIKE Cryptosystem

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.

• Publication year

  2024

• Venue

  Des. Codes Cryptogr.

• Publication date

  2024-10-14

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.48550/arXiv.2410.11111arXiv 2410.11111
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Error floor prediction with Markov models for QC-MDPC codes

  2025cited by this paper
• Exploring Decryption Failures of BIKE: New Class of Weak Keys and Key Recovery Attacks

  2023influential reference
• A Study of Error Floor Behavior in QC-MDPC Codes

  2022influential reference
• Weak-Key Analysis for BIKE Post-Quantum Key Encapsulation Mechanism

  2022influential reference
• Performance bounds for QC-MDPC codes decoders

  2021cited by this paper
• Analysis of In-Place Randomized Bit-Flipping Decoders for the Design of LDPC and MDPC Code-Based Cryptosystems

  2020cited by this paper
• About Low DFR for QC-MDPC Decoding

  2020cited by this paper
• Counting Short Cycles in Bipartite Graphs: A Fast Technique/Algorithm and a Hardness Result

  2020influential reference
• On the Existence of Weak Keys for QC-MDPC Decoding

  2020influential reference
• A Class of Weak Keys for the QC-MDPC Cryptosystem

  2020influential reference
• On constant-time QC-MDPC decoding with negligible failure rate

  2019influential reference
• Analysis of the Error Correction Capability of LDPC and MDPC Codes Under Parallel Bit-Flipping Decoding and Application to Cryptography

  2019cited by this paper
• The Decoding Failure Probability of MDPC Codes

  2018cited by this paper
• Analytical Lower Bound on the Lifting Degree of Multiple-Edge QC-LDPC Codes With Girth 6

  2018cited by this paper
• A Key Recovery Attack on MDPC with CCA Security Using Decoding Errors

  2016cited by this paper
• Weak Keys for the Quasi-Cyclic MDPC Public Key Encryption Scheme

  2016cited by this paper
• MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes

  2013cited by this paper
• Construction of High-Rate Regular Quasi-Cyclic LDPC Codes Based on Cyclic Difference Families

  2012cited by this paper
• On the Construction of Structured LDPC Codes Free of Small Trapping Sets

  2012cited by this paper
• Grover vs. McEliece

  2010cited by this paper
• Analysis of Absorbing Sets and Fully Absorbing Sets of Array-Based LDPC Codes

  2009cited by this paper
• A New Analysis of the McEliece Cryptosystem Based on QC-LDPC Codes

  2008cited by this paper
• Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC Codes

  2007cited by this paper
• Which Codes Have$4$-Cycle-Free Tanner Graphs?

  2006cited by this paper
• Pseudocodewords of Tanner Graphs

  2005cited by this paper
• Quasicyclic low-density parity-check codes from circulant permutation matrices

  2004cited by this paper
• Finite-length analysis of low-density parity-check codes on the binary erasure channel

  2002cited by this paper
• Using low density parity check codes in the McEliece cryptosystem

  2000cited by this paper
• Which codes have cycle-free Tanner graphs?

  1998cited by this paper
• Near Shannon Limit Performance of Low Density Parity Check Codes

  1996cited by this paper
• Codes and Decoding on General Graphs

  1996cited by this paper
• Near Shannon limit performance of low density parity check codes

  1996cited by this paper
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

  1995cited by this paper
• Algorithms for quantum computation: discrete logarithms and factoring

  1994cited by this paper
• A recursive approach to low complexity codes

  1981cited by this paper
• On the inherent intractability of certain coding problems (Corresp.)

  1978cited by this paper
• A public key cryptosystem based on algebraic coding theory

  1978cited by this paper

• No citing papers are available for this paper.