On the security of the McEliece public-key cryptosystern

As RSA, the McEliece public-key cryptosystem has successfully resisted more than 20 years of cryptanalysis effort. However, despite the fact that it is faster, it was not as successful as RSA as far as applications are concerned. This is certainly due to its very large public key and probably also to the belief that the system could not be used for the design of a digital signature scheme. We present here the state of art of the implementation and the security of the two main variants of code-based public-key encryption schemes (McEliece's and Niedereitter's) as well as the more recent signature scheme derived from them. We also show how it is possible to formally reduce the security of these systems to two well identified algorithmic problems. The decoding attack (aimed on one particular ciphertext) is connected to the NP-complete syndrome decoding problem. The structural attack (aimed on the public key) is connected to the problem of distinguishing binary Goppa codes from random codes. We conjecture that both these problems are difficult and present some arguments to support this claim.