A Code-specific Conservative Model for the Failure Rate of Bit-flipping Decoding of LDPC Codes with Cryptographic Applications
This work addresses the need for secure code-based cryptosystems by ensuring reliable decoding and weak key detection, representing an incremental improvement in cryptographic applications.
The authors tackled the problem of characterizing the decoding failure rate of LDPC/MDPC codes for cryptographic applications by providing a statistical worst-case analysis of a modified iterative bit-flipping decoder. This analysis enabled deriving a code-specific bound on the failure rate and worst-case behavior, supporting the construction of cryptosystems with δ-correctness and identification of weak keys.
Characterizing the decoding failure rate of iteratively decoded Low- and Moderate-Density Parity Check (LDPC/MDPC) codes is paramount to build cryptosystems based on them, able to achieve indistinguishability under adaptive chosen ciphertext attacks. In this paper, we provide a statistical worst-case analysis of our proposed iterative decoder obtained through a simple modification of the classic in-place bit-flipping decoder. This worst case analysis allows both to derive the worst-case behaviour of an LDPC/MDPC code picked among the family with the same length, rate and number of parity checks, and a code-specific bound on the decoding failure rate. The former result allows us to build a code-based cryptosystem enjoying the $δ$-correctness property required by IND-CCA2 constructions, while the latter result allows us to discard code instances which may have a decoding failure rate significantly different from the average one (i.e., representing weak keys), should they be picked during the key generation procedure.