pith. sign in

arxiv: 2604.18247 · v1 · submitted 2026-04-20 · 💻 cs.IT · math.IT

Near-Codewords Aware Bit Flipping Decoding of QC-MDPC Codes

Alessio Baldelli , Marco Baldi , Davide De Zuane , Paolo Santini This is my paper

Pith reviewed 2026-05-10 03:50 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords QC-MDPC codesbit-flipping decodingnear-codewordsdecoding failure rateBIKEpost-quantum cryptographytrapping setserror patterns
0
0 comments X

The pith

Any bit-flipping decoder for QC-MDPC codes can be modified to detect near-codewords and recover from the error patterns they cause with minimal added computation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Bit-flipping decoders used in post-quantum schemes such as BIKE fail mainly because of near-codewords, which are low-weight error patterns tied to low-weight syndromes. The paper shows that any such decoder can be adjusted to recognize when it has entered a configuration caused by a near-codeword and then escape that state. The adjustment requires only a small increase in operations. Simulations on both small test codes and full BIKE parameters for NIST category 1 produce large drops in the decoding failure rate. After the change, a recent BF variant called BF-Max performs better than the two decoders chosen for BIKE.

Core claim

We show that any BF decoder can be tweaked and made 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.

What carries the argument

The near-codeword awareness tweak, which lets the decoder identify overlaps or syndromes indicating a near-codeword and adjust its flipping decisions to escape the associated trapping set.

If this is right

  • Drastic reductions in the decoding failure rate occur for both toy QC-MDPC codes and full BIKE parameters.
  • The modification adds only minimal computational overhead to any existing bit-flipping decoder.
  • A modified BF-Max decoder outperforms the two decoders currently used in BIKE.
  • The same awareness change can be applied to every member of the bit-flipping decoder family.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Schemes that rely on QC-MDPC codes could reach the required security level with smaller margins on the failure rate target.
  • The approach may reduce the need to switch to more complex decoders when scaling to higher security categories.
  • Similar detection of analogous low-weight structures could be tested on other moderate-density parity-check code families.

Load-bearing premise

Near-codewords are the main source of failures at very low decoding failure rates and the awareness change can be added to any bit-flipping decoder without creating new failure modes or large extra cost.

What would settle it

Simulations of the modified decoders on BIKE parameters at the target security level that show no meaningful drop in decoding failure rate or that add more than a few percent extra operations per iteration.

Figures

Figures reproduced from arXiv: 2604.18247 by Alessio Baldelli, Davide De Zuane, Marco Baldi, Paolo Santini.

Figure 1
Figure 1. Figure 1: Experimental distribution of counters for bad bits (in blue) and [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Decoding failure probabilities on pt, uq-almost near-codewords for codes with r “ 12323, v “ 71 and t “ 134. Continuous lines are referred to standard decoders, dotted lines to modified decoders. For each value of u, decoding of 108 random almost near-codewords has been simulated. appears less important is not surprising, since, for such two decoders, we do not control the number of flipped bits. That is, … view at source ↗
Figure 2
Figure 2. Figure 2: DFR of double-circulant codes (r “ 2003), for several decoders and values of v. Continuous and dotted lines refer to the standard and the TS-aware decoder, respectively. Each point has been estimated after (at least) 30 decoding failures. TABLE I OoP DECODER THRESHOLDS USED IN FIG. 2C. v Thresholds 9 p9, 8, 8, 8, 8, 7, 7, 7, 6, 6, 6, 6, 5, 5, 5q 11 p11, 10, 10, 9, 9, 8, 8, 8, 7, 7, 7, 7, 6, 6, 6q 13 p13, 1… view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a lightweight modification to bit-flipping (BF) decoders for QC-MDPC codes that adds awareness of near-codewords (low-weight error patterns linked to low-weight syndromes), allowing the decoder to recognize and escape trapping sets. The authors claim this incurs minimal overhead and, via simulations on toy parameters and BIKE NIST category-1 sizes, produces drastic DFR reductions; they further report that the modified BF-Max variant outperforms the BIKE reference decoders.

Significance. If the near-codeword heuristic generalizes, the work offers a practical, low-cost route to lower DFR in QC-MDPC-based post-quantum schemes such as BIKE. The generality across multiple BF variants and the empirical demonstration of improvement constitute the main strengths; however, the absence of results at cryptographic block lengths and DFR targets below 10^{-10} limits immediate applicability.

major comments (2)
  1. [Numerical Simulations] Numerical Simulations section: DFR reductions are reported only for toy codes and BIKE category-1 parameters (n on the order of 10^4). No data, scaling analysis, or extrapolation is provided for the larger n and DFR << 10^{-10} regime required for cryptographic security, leaving the central claim that the heuristic remains effective and low-overhead at deployment scales unsupported.
  2. [Proposed Decoder Modification] Proposed Decoder Modification section: The precise implementation of near-codeword awareness (how bad configurations are detected and corrected) is described at a high level only; without pseudocode, complexity counts, or memory requirements, the repeated assertion of 'minimal computational overhead' cannot be verified and is load-bearing for the practicality claim.
minor comments (2)
  1. [Introduction] The abstract and introduction cite prior works for near-codeword dominance but do not include a self-contained check (e.g., syndrome-weight histograms or overlap statistics) within the presented simulations.
  2. [Numerical Simulations] Figure captions and axis labels in the DFR plots should explicitly state the number of Monte-Carlo trials and any confidence intervals; current presentation makes it difficult to assess statistical reliability of the reported reductions.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for the constructive feedback, which helps clarify the scope and presentation of our results. We respond to each major comment below and indicate the revisions planned for the updated manuscript.

read point-by-point responses

  1. Referee: [Numerical Simulations] Numerical Simulations section: DFR reductions are reported only for toy codes and BIKE category-1 parameters (n on the order of 10^4). No data, scaling analysis, or extrapolation is provided for the larger n and DFR << 10^{-10} regime required for cryptographic security, leaving the central claim that the heuristic remains effective and low-overhead at deployment scales unsupported.

    Authors: We acknowledge this limitation in the current manuscript. Our simulations were designed to demonstrate the heuristic's effectiveness where extensive Monte Carlo trials remain computationally tractable. In the revised version we will add a new subsection on scalability that explains why the near-codeword targeting mechanism (the dominant failure mode at low DFR per recent literature) is expected to preserve its benefit at larger block lengths, together with a simple extrapolation model based on the observed reduction factors. Direct simulation at full cryptographic sizes and DFR targets below 10^{-10} is, however, infeasible with available resources, as it would require orders-of-magnitude more trials than performed here. revision: partial

  2. Referee: [Proposed Decoder Modification] Proposed Decoder Modification section: The precise implementation of near-codeword awareness (how bad configurations are detected and corrected) is described at a high level only; without pseudocode, complexity counts, or memory requirements, the repeated assertion of 'minimal computational overhead' cannot be verified and is load-bearing for the practicality claim.

    Authors: We agree that the description is currently high-level and insufficient for independent verification. In the revised manuscript we will insert pseudocode for the modified decoder in an appendix and add a dedicated complexity paragraph. The analysis will show that near-codeword awareness requires only a constant number of additional overlap and weight checks per iteration (approximately 10-15% overhead) and stores a modest list of representative low-weight patterns whose memory footprint is negligible relative to the parity-check matrix. These additions will substantiate the minimal-overhead claim. revision: yes

standing simulated objections not resolved
  • Empirical results at full cryptographic block lengths and DFR targets below 10^{-10}, which remain computationally prohibitive.

Circularity Check

0 steps flagged

No circularity: empirical validation of algorithmic tweak via fresh simulations

full rationale

The paper introduces a lightweight modification to existing BF decoders that incorporates awareness of near-codewords (identified via low-weight syndromes) and then demonstrates DFR reductions through direct numerical simulations on both toy parameters and BIKE NIST category-1 sizes. No derivation chain, fitted parameter, or prediction is shown to reduce by construction to prior inputs or self-citations; the central result is the observed performance gain from the proposed heuristic, which is externally falsifiable via the reported experiments. Self-citations, if present for background on near-codewords, are not load-bearing for the new modification or its measured outcomes.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The work is algorithmic and simulation-based; the abstract introduces no free parameters, mathematical axioms, or new postulated entities.

pith-pipeline@v0.9.0 · 5541 in / 1012 out tokens · 47496 ms · 2026-05-10T03:50:23.865181+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    MDPC-McEliece: New McEliece variants from moderate density parity-check codes,

    R. Misoczki, J.-P. Tillich, N. Sendrier, and P. S. Barreto, “MDPC-McEliece: New McEliece variants from moderate density parity-check codes,” inProc. IEEE International Symposium on Information Theory (ISIT), 2013, pp. 2069–2073

    work page 2013

  2. [2]

    Aragon et al., “Bike,”NIST PQC Submission, 2020

    N. Aragon et al., “Bike,”NIST PQC Submission, 2020

    work page 2020

  3. [3]

    LEDAcrypt: QC-LDPC code-based cryp- tosystems with bounded decryption failure rate,

    M. Baldi, A. Barenghi, F. Chiaraluce, G. Pelosi, and P. Santini, “LEDAcrypt: QC-LDPC code-based cryp- tosystems with bounded decryption failure rate,” in Code-Based Cryptography, M. Baldi, E. Persichetti, and P. Santini, Eds., Cham: Springer International Publishing, 2019, pp. 11–43,ISBN: 978-3-030-25922- 8

    work page 2019

  4. [4]

    QC-MDPC decoders with several shades of gray,

    N. Drucker, S. Gueron, and D. Kostic, “QC-MDPC decoders with several shades of gray,” inProc. Inter- national Conference on Post-Quantum Cryptography, Springer, 2020, pp. 35–50

    work page 2020

  5. [5]

    On the decoding failure rate of QC-MDPC bit-flipping decoders,

    N. Sendrier and V . Vasseur, “On the decoding failure rate of QC-MDPC bit-flipping decoders,” inProc. Post-Quantum Cryptography: 10th International Con- ference, PQCrypto 2019, Chongqing, China, May 8– 10, 2019 Revised Selected Papers 10, Springer, 2019, pp. 404–416

    work page 2019

  6. [6]

    Post-quantum cryptography: A study of the decoding of QC-MDPC codes,

    V . Vasseur, “Post-quantum cryptography: A study of the decoding of QC-MDPC codes,” Ph.D. dissertation, Université Paris Cité, 2021

    work page 2021

  7. [7]

    Alagic et al.,Status report on the fourth round of the nist post-quantum cryptography standardization pro- cess

    G. Alagic et al.,Status report on the fourth round of the nist post-quantum cryptography standardization pro- cess. US Department of Commerce, National Institute of Standards and Technology, 2025

    work page 2025

  8. [8]

    A key recov- ery attack on MDPC with CCA security using decoding errors,

    Q. Guo, T. Johansson, and P. Stankovski, “A key recov- ery attack on MDPC with CCA security using decoding errors,” inProc. International conference on the theory and application of cryptology and information security, Springer, 2016, pp. 789–815

    work page 2016

  9. [9]

    A modular analysis of the Fujisaki-Okamoto transformation,

    D. Hofheinz, K. Hövelmanns, and E. Kiltz, “A modular analysis of the Fujisaki-Okamoto transformation,” in Theory of Cryptography Conference, Springer, 2017, pp. 341–371

    work page 2017

  10. [10]

    Bit-flipping decoder failure rate estimation for (v,w)-regular codes,

    A. Annechini, A. Barenghi, and G. Pelosi, “Bit-flipping decoder failure rate estimation for (v,w)-regular codes,”

    work page

  11. [11]

    [Online]

    arXiv: 2401.16919[cs.CR]. [Online]. Avail- able: https://arxiv.org/abs/2401.16919

    work page arXiv

  12. [12]

    BF-Max: An efficient bit flipping decoder with pre- dictable decoding failure rate,

    A. Baldelli, M. Baldi, F. Chiaraluce, and P. Santini, “BF-Max: An efficient bit flipping decoder with pre- dictable decoding failure rate,” inproc. IEEE Interna- tional Symposium on Information Theory (ISIT), 2025, pp. 1–6

    work page 2025

  13. [13]

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

    S. Arpin et al., “Error floor prediction with Markov models for QC-MDPC codes,”Cryptology ePrint Archive, 2025

    work page 2025

  14. [14]

    A study of error floor behavior in QC-MDPC codes,

    S. Arpin, T. R. Billingsley, D. R. Hast, J. B. Lau, R. Perlner, and A. Robinson, “A study of error floor behavior in QC-MDPC codes,” inProc. International Conference on Post-Quantum Cryptography, Springer, 2022, pp. 89–103

    work page 2022

  15. [15]

    About low DFR for QC-MDPC decoding,

    N. Sendrier and V . Vasseur, “About low DFR for QC-MDPC decoding,” inProc. International Confer- ence on Post-Quantum Cryptography, Springer, 2020, pp. 20–34

    work page 2020

  16. [16]

    The decoding failure probability of MDPC codes,

    J.-P. Tillich, “The decoding failure probability of MDPC codes,” inProc. IEEE International Symposium on Information Theory (ISIT), 2018, pp. 941–945

    work page 2018

  17. [17]

    Performance bounds for QC-MDPC codes decoders,

    M. Baldi, A. Barenghi, F. Chiaraluce, G. Pelosi, and P. Santini, “Performance bounds for QC-MDPC codes decoders,” inCode-Based Cryptography Workshop, Springer, 2021, pp. 95–122

    work page 2021

  18. [18]

    Ouzan and Y

    S. Ouzan and Y . Be’ery,Moderate-density parity-check codes, 2009. arXiv: 0911.3262[cs.IT]

    work page arXiv 2009

  19. [19]

    Cryptanalysis of a new instance of McEliece cryptosystem based on QC- LDPC codes,

    M. Baldi and F. Chiaraluce, “Cryptanalysis of a new instance of McEliece cryptosystem based on QC- LDPC codes,” in2007 IEEE International Symposium on Information Theory, 2007, pp. 2591–2595

    work page 2007

  20. [20]

    Hard-decision iterative decoding of LDPC codes with bounded error rate,

    P. Santini, M. Battaglioni, M. Baldi, and F. Chiaraluce, “Hard-decision iterative decoding of LDPC codes with bounded error rate,” inProc. IEEE International Con- ference on Communications (ICC), 2019, pp. 1–6

    work page 2019