Using Non-Binary LDPC and MDPC Codes in the McEliece Cryptosystem

In this paper we study the use of non-binary Low-Density Parity-Check and Moderate-Density Parity-Check codes for the McEliece cryptosystem. We generalize existing constructions by using codes and errors that are both nonbinary. We devise a decoding technique which is inspired by the binary Bit Flipping decoder and whose complexity grows linearly with the code length. We show that the non-binary schemes are potentially able to reach the same security levels of the binary ones, for equal or smaller key sizes, but with reduced decryption failure rate, the latter being a relevant parameter in view of countering statistical attacks.