The algorithm has never gained much acceptance in the cryptographic community, but is a candidate for "post-quantum cryptography", as it is immune to attacks using Shor's algorithm and – more generally – measuring coset states using Fourier sampling.
[2] The algorithm is based on the hardness of decoding a general linear code (which is known to be NP-hard[3]).
For a description of the private key, an error-correcting code is selected for which an efficient decoding algorithm is known, and that is able to correct
is perturbated by two randomly selected invertible matrices
Variants of this cryptosystem exist, using different types of codes.
Most of them were proven less secure; they were broken by structural decoding.
The most effective attacks known use information-set decoding algorithms.
[5] Another paper shows that for quantum computing, key sizes must be increased by a factor of four due to improvements in information set decoding.
[7] For a long time, it was thought that McEliece could not be used to produce signatures.
One of the main disadvantages of McEliece is that the private and public keys are large matrices.
For a standard selection of parameters, the public key is 512 kilobits long.
All users in a McEliece deployment share a set of common security parameters:
from some family of codes for which she knows an efficient decoding algorithm, and to make
public knowledge but keep the decoding algorithm secret.
Therefore, Alice may publish a suitably obfuscated generator matrix of
More specifically, the steps are as follows: Suppose Bob wishes to send a message m to Alice whose public key is
, Alice performs the following steps to decrypt the message: Note that
[8][9] McEliece originally suggested security parameter sizes of
Recent analysis suggests parameter sizes of
when using list decoding for the Goppa code, giving rise to public key sizes of 520047 and 460647 bits respectively.
with Goppa code were proposed, giving the size of public key of 8373911 bits.
An attack consists of an adversary, who knows the public key
but not the private key, deducing the plaintext from some intercepted ciphertext
Decoding a general linear code, however, is known to be NP-hard,[3] however, and all of the above-mentioned methods have exponential running time.
In 2008, Bernstein, Lange, and Peters[5] described a practical attack on the original McEliece cryptosystem, using the information set decoding method by Stern.
[11] Using the parameters originally suggested by McEliece, the attack could be carried out in 260.55 bit operations.
Since the attack is embarrassingly parallel (no communication between nodes is necessary), it can be carried out in days on modest computer clusters.
Many code families have been proposed for McEliece, and most of them have been completely "broken" in the sense that attacks have been found that recover an efficient decoding algorithm, such as Reed-Solomon codes.
The originally proposed binary Goppa codes remain one of the few suggested families of codes that have largely resisted attempts at devising structural attacks.
A variant of this algorithm combined with NTS-KEM[12] was entered into and selected during the third round of the NIST post-quantum encryption competition.