The decoding failure probability of MDPC codes

International audienceModerate Density Parity Check (MDPC) codes are defined here as codes which have a parity-check matrix whose row weight is of order the square root of the length n of the code. They can be decoded like LDPC codes but they decode much less errors than LDPC codes: the number of errors they can decode in this case is of order the square root of n. Despite this fact they have been proved very useful in cryptography for devising key exchange mechanisms [BGG + 17]. They have also been proposed in McEliece type cryptosystems. However in this case, the parameters that have been proposed in [MTSB13] were broken in [GJS16]. This attack exploits the fact that the decoding failure probability is non-negligible. We show here that this attack can be thwarted by choosing the parameters in a more conservative way. We first show that such codes can decode with a simple bit-flipping decoder any pattern of O √ n log log n log n errors. This avoids the previous attack at the cost of significantly increasing the key size of the scheme. We then show that under a very reasonable assumptions the error probability after decoding decays almost exponentially with the codelength with just two iterations of bit-flipping. With an additional assumption it has even been proved that it decays exponentially with an unbounded number of iterations and show that in this case the increase of the key size which is required for resisting to the [GJS16] attack is only moderate