Certified Finite-Key Minimum-Distance Bounds for Sparse QC-MDPC Ensembles: The BIKE Case and a Cyclotomic-Kernel Extension

Jeff Pickhardt

Loading document…

Certified Finite-Key Minimum-Distance Bounds for Sparse QC-MDPC Ensembles: The BIKE Case and a Cyclotomic-Kernel Extension

Abstract

We first prove an exact, non-asymptotic upper bound on the probability that a BIKE-type quasi-cyclic moderate-density parity-check code contains a low-weight codeword. For the BIKE parameter condition that the block length r is prime and 2 is primitive modulo r, the proof combines a fixed-weight-shell injectivity lemma in F2[x]/(xr−1) with full-length simultaneous- shift orbits. It yields exact integer-certified minimum-distance bounds for all three BIKE v5.2 parameter sets. We then remove the irreducibility hypothesis at the structural level. For arbitrary odd block length, binary cyclotomic cosets decompose xr−1 into simple components. Every possible failure of shell injectivity is captured by a cyclic multiplication-kernel code Ka, and the low-weight spectrum is controlled by the intersection of cosets of Ka with the constant-weight secret shell. This gives a factorization-sensitive theorem with exact orbit, unit-shell, and kernel-spectrum terms. For prime rwith ordr (2) = (r−1)/2, the classical square-root bound for binary quadratic residue codes implies that, whenever 4d2 <r, the original BIKE-form bound holds unchanged even though (xr−1)/(x−1) is reducible. No decoder-iteration independence or distributional heuristic is used.

File Details

v1 bike_qcmdpc_cyclotomic_extension.pdf