McEliece

The McEliece cryptosystem is a public-key cryptosystem based on error-correcting codes, proposed by Robert J. McEliece in 1978. It uses a linear code with an efficient decoding algorithm, most commonly a binary Goppa code. The public key is a generator matrix of a code that is indistinguishable from a random code, obtained by masking the original code with a random permutation and a non-singular transformation. The private key consists of the original code together with its efficient decoding algorithm.

Encryption converts a message into a codeword of the public code and then adds a deliberately chosen error vector of a fixed Hamming weight. The resulting ciphertext is sent to the recipient. Decryption uses the private decoding algorithm to correct the errors and recover the original codeword, from which the message is recovered.

Security and characteristics: The security of McEliece rests on the hardness of decoding a random linear code, a problem that has resisted decades of cryptanalytic effort. It is widely regarded as resistant to known practical quantum attacks, making it a leading candidate for post-quantum cryptography. A major drawback is the large size of the public key, typically hundreds of kilobytes for standard security levels, which motivates development of variants that aim to reduce key size.

Variants and developments: In practice, the Niederreiter variant, alternative codes, and structured disguises have been explored to balance key size and security. Despite attempts to reduce key size, the classic McEliece design remains one of the most studied code-based cryptosystems and has influenced standards discussions in the post-quantum landscape.