Analysis of In-Place Randomized Bit-Flipping Decoders for the Design of LDPC and MDPC Code-Based Cryptosystems

We present a variant of the classic in-place bit-flipping decoder, frequently used with Low- and Moderate-Density Parity Check (LDPC/MDPC) codes, which allows a statistical analysis of the achievable decoding failure rate (DFR) in worst-case conditions. Such evaluation is of paramount importance in code-based post-quantum cryptography (PQC) where the ability to achieve indistinguishability under adaptive chosen ciphertext attacks strictly depends on being able to ensure very low DFR values (e.g., in the order of 2 - 128 or lower) that, as such, are practically impossible to validate via numerical simulation. We provide theoretical evidence of the proposed approach and demonstrate its correctness through numerical examples. Moreover, we investigate the effect of changing the bit flipping decision threshold on the provided worst case analysis. Finally, we give design parameters for code-based cryptosystems employing Quasi-Cyclic LDPC/MDPC codes, able to achieve the security levels required in the NIST PQC standardization initiative which is currently in progress.