McEliece cryptosystem

The principle is that Alice chooses a linear code ${\displaystyle C}$ from some family of codes for which she knows an efficient decoding algorithm, and to make ${\displaystyle C}$ public knowledge but keep the decoding algorithm secret. Such a decoding algorithm requires not just knowing ${\displaystyle C}$, in the sense of knowing an arbitrary generator matrix, but requires one to know the parameters used when specifying ${\displaystyle C}$ in the chosen family of codes. For instance, for binary Goppa codes, this information would be the Goppa polynomial and the code locators. Therefore, Alice may publish a suitably obfuscated generator matrix of ${\displaystyle C}$.

More specifically, the steps are as follows:

1. Alice selects a binary ${\displaystyle (n,k)}$-linear code ${\displaystyle C}$ capable of (efficiently) correcting ${\displaystyle t}$ errors from some large family of codes, e.g. binary Goppa codes. This choice should give rise to an efficient decoding algorithm ${\displaystyle A}$. Let also ${\displaystyle G}$ be any generator matrix for ${\displaystyle C}$. Any linear code has many generator matrices, but often there is a natural choice for this family of codes. Knowing this would reveal ${\displaystyle A}$ so it should be kept secret.
2. Alice selects a random ${\displaystyle k\times k}$ binary non-singular matrix ${\displaystyle S}$.
3. Alice selects a random ${\displaystyle n\times n}$ permutation matrix ${\displaystyle P}$.
4. Alice computes the ${\displaystyle k\times n}$ matrix ${\displaystyle {\hat {G}}=SGP}$.
5. Alice's public key is ${\displaystyle ({\hat {G}},t)}$; her private key is ${\displaystyle (S,P,A)}$. Note that ${\displaystyle A}$ could be encoded and stored as the parameters used for selecting ${\displaystyle C}$.

Suppose Bob wishes to send a message m to Alice whose public key is ${\displaystyle ({\hat {G}},t)}$:

1. Bob encodes the message ${\displaystyle m}$ as a binary string of length ${\displaystyle k}$.
2. Bob computes the vector ${\displaystyle c^{\prime }=m{\hat {G}}}$.
3. Bob generates a random ${\displaystyle n}$-bit vector ${\displaystyle z}$ containing exactly ${\displaystyle t}$ ones (a vector of length ${\displaystyle n}$ and weight ${\displaystyle t}$)[1]
4. Bob computes the ciphertext as ${\displaystyle c=c^{\prime }+z}$.

Upon receipt of ${\displaystyle c}$, Alice performs the following steps to decrypt the message:

1. Alice computes the inverse of ${\displaystyle P}$ (i.e. ${\displaystyle P^{-1}}$).
2. Alice computes ${\displaystyle {\hat {c}}=cP^{-1}}$.
3. Alice uses the decoding algorithm ${\displaystyle A}$ to decode ${\displaystyle {\hat {c}}}$ to ${\displaystyle {\hat {m}}}$.
4. Alice computes ${\displaystyle m={\hat {m}}S^{-1}}$.

The attacker knows ${\displaystyle {\hat {G}}}$ which is the generator matrix of an ${\displaystyle (n,k)}$ code ${\displaystyle {\hat {C}}}$ which is combinatorially able to correct ${\displaystyle t}$ errors. The attacker may ignore the fact that ${\displaystyle {\hat {C}}}$ is really the obfuscation of a structured code chosen from a specific family, and instead just use an algorithm for decoding with any linear code. Several such algorithms exist, such as going through each codeword of the code, syndrome decoding, or information set decoding.

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 2^60.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.

The attacker may instead attempt to recover the "structure" of ${\displaystyle C}$, thereby recovering the efficient decoding algorithm ${\displaystyle A}$ or another sufficiently strong, efficient decoding algorithm.

The family of codes from which ${\displaystyle C}$ is chosen completely determines whether this is possible for the attacker. Many code families have been proposed for McEliece, and most of them have been completely "broken" in the sense that attacks which recover an efficient decoding algorithm has been found, such as Reed-Solomon codes.

The originally proposed binary Goppa codes remain one of the few suggested families of codes which have largely resisted attempts at devising structural attacks.