Improved iterative decoding of QC-MDPC codes in the McEliece public key cryptosystem

We improve iterative decoding of the moderate density parity-check codes, recently suggested as code candidates in the McEliece public key cryptosystem. In case of bit-flipping (BF) decoder failure, the code parity-check matrix is extended by adding auxiliary variable nodes based on reliability information from the BF decoder. Then iterative decoding is applied to the extended parity-check matrix. The proposed decoding algorithm is analyzed and its frame error rate performance is compared to the same performance of both the best implementations of BF decoding and its modifications. It is demonstrated an improved performance for the iterative decoding step in decryption, which allows to increase the resistance against recent attacks based on taking advantage of the somewhat large failure probability of the BF algorithm.