MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes
Cryptography based on coding theory is believed to resist to quantum attacks (all cryptosystems based on factoring/discrete logarithm can be quantum attacked in polynomial time). The McEliece cryptosystem is the oldest code-based cryptosystem and its security relies on two problems: the indistinguishability of the code family and the hardness of decoding random linear codes. The former is usually the weakest one. The main drawback of this cryptosystem regards its huge public-keys. Recently, several attempts to reduce its key-size have been proposed. Almost all of them were successfully broken due to the additional algebraic structure used to reduce the keys. In this paper, the authors propose McEliece variants from Moderate Density Parity-Check codes. These codes are LDPC codes of higher density than what is usually adopted for telecommunication solutions.