In this book, we have mostly described cryptographic systems that are based on number theoretic principles. There are many other cryptosystems that are based on other complex problems. Here we present one based on the difficulty of finding the nearest codeword for a linear binary code.

The idea is simple. Suppose you have a binary string of length 1024 that has 50 errors. There are $({\phantom{\text{.}}}_{\phantom{5}50}^{1024})\approx 3\times {10}^{85}$ possible locations for these errors, so an exhaustive search that tries all possibilities is infeasible. Suppose, however, that you have an efficient decoding algorithm that is unknown to anyone else. Then only you can correct these errors and find the corrected string. McEliece showed how to use this to obtain a public key cryptosystem.

Bob chooses $G$ to be the generating matrix for an $(n\text{,}k)$ linear error correcting code $C$ with $d(C)=d$. He chooses $S$ to be a $k\times k$ matrix that is invertible mod 2 and lets $P$ be an $n\times n$ permutation matrix, which means that $P$ has exactly one 1 in every row and in every column, with all the other entries being 0. Define

The matrix $G_1$ is the public key for the cryptosystem. Bob keeps $S\text{,}G\text{,}P$ secret.

In order for Alice to send Bob a message $x$, she generates a random binary string $e$ of length $n$ that has weight $t$. She forms the ciphertext by computing

Bob decrypts $y$ as follows:

1. Calculate $y_1\equiv y{P}^{-1}$. (Since $P$ is a permutation matrix, $e_1=e{P}^{-1}$ is still a binary string of weight $t$. We have $y_1\equiv xSG+e_1$.)

2. Apply the error decoder for the code $C$ to $y_1$ to correct the “error” and obtain the codeword $x_1$ closest to $y_1$.

3. Compute $x_0$ such that $x_{0}G\equiv x_1$ (in the examples we have considered, $x_0$ is simply the first $k$ bits of $x_1$).

4. Compute $x\equiv x_0{S}^{-1}$.

The security of the system lies in the difficulty of decoding $y_1$ to obtain $x_1$. There is a little security built into the system by $S$; however, once a decoding algorithm is known for the code generated by $GP$, a chosen plaintext attack allows one to solve for the matrix $S$ (as in the Hill cipher).

To make decoding difficult, $d(C)$ should be chosen to be large. McEliece suggested using a $[1024\text{,}512\text{,}101]$ Goppa code. The Goppa codes have parameters of the form $n=2^m\text{,}d=2t+1\text{,}k=n-mt$. For example, taking $m=10$ and $t=50$ yields the $[1024\text{,}524\text{,}101]$ code just mentioned. It can correct up to 50 errors. For given values of $m$ and $t$, there are in fact many inequivalent Goppa codes with these parameters. We will not discuss these codes here except to mention that they have an efficient decoding algorithm and therefore can be used to correct errors quickly.

The McEliece system seems to be reasonably secure. For a discussion of its security, see [Chabaud]. A disadvantage of the system compared to RSA, for example, is that the size of the public key $G_1$ is rather large.