Near-Codewords Aware Bit Flipping Decoding of QC-MDPC Codes
For post-quantum cryptography schemes like BIKE, this work improves decoding reliability at very low DFR values, which is critical for practical deployment.
The paper introduces a modification to Bit-Flipping decoders for QC-MDPC codes that makes them aware of near-codewords, enabling recovery from trapping sets. This results in drastic reductions in Decoding Failure Rate (DFR) with minimal computational overhead, and the modified BF-Max decoder outperforms the two decoders used by BIKE for NIST security category 1.
Bit-Flipping (BF) decoders are a family of decoders widely employed in post-quantum cryptographic schemes based on Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) codes, such as BIKE. BF decoders suffer from trapping sets, corresponding to low-weight error patterns that likely lead to decoding failures. For QC-MDPC codes, the most relevant family of trapping sets is that of near-codewords, which are error patterns associated to low-weight syndromes. Indeed, recent works show that error patterns having a large overlap with near-codewords are the main culprits for decoding failures at very low Decoding Failure Rate (DFR) values. In this paper, we show that any BF decoder can be tweaked and made somehow aware of near-codewords, which means being able to recognize, and recover from, bad configurations due to near-codewords. We show that this modification results in minimal computational overhead. Through intensive numerical simulations, we evaluate the effectiveness of this approach on several BF decoders, considering both toy code parameters and BIKE parameters for NIST security category 1. Our results show drastic reductions in the DFR. We also find that, with this modification, a recently proposed BF variant called BF-Max outperforms the two decoders used by BIKE within the NIST competition.