What is the McEliece Cryptosystem?

The McEliece cryptosystem [Mce78] is a public-key encryption algorithm based on algebraic coding theory. The system uses a class of error-correcting codes, known as the Goppa codes, for which fast decoding algorithms exist. The basic idea is to construct a Goppa code as the private key and disguise it as a general linear code, which is the public key. The general linear code cannot be easily decoded unless the corresponding private matrix is known.

The McEliece cryptosystem has a number of drawbacks. These include large public-key size (in excess of one megabit), substantial expansion of data, and possibly a certain similarity to the knapsack cryptosystem. Korzhik and Turkin [KT91] reported a polynomial-time attack on the system, but it is not yet clear whether the attack is effective. Gabidulin, Paramonov, and Tretjakov [GPT91] proposed a modification of the McEliece cryptosystem by replacing Goppa codes with a different algebraic code and claimed that the new version was more secure than the original system. However, Gibson [Gib93] later showed that there was not really any advantage to the new version.