# 24.10 The McEliece Cryptosystem

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{\rule{negativethinmathspace}{0ex}}\phantom{\rule{negativethinmathspace}{0ex}}{\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{,}\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{,}\text{}G\text{,}\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:

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}$.)

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}$.

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}$).

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{,}\text{}512\text{,}\text{}101]$ Goppa code. The **Goppa codes** have parameters of the form $n={2}^{m}\text{,}\text{}d=2t+1\text{,}\text{}k=n-mt$. For example, taking $m=10$ and $t=50$ yields the $[1024\text{,}\text{}524\text{,}\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.

# Example

Consider the matrix

which is the generator matrix for the $[7\text{,}\text{}4]$ Hamming code. Suppose Alice wishes to send a message

to Bob. In order to do so, Bob must create an invertible matrix $S$ and a random permutation matrix $P$ that he will keep secret. If Bob chooses

and

Using these, Bob generates the public encryption matrix

In order to encrypt, Alice generates her own random error vector $e$ and calculates the ciphertext $y=x{G}_{1}+e$. In the case of a Hamming code the error vector has weight $1$. Suppose Alice chooses

Then

Bob decrypts by first calculating

Calculating the syndrome of ${y}_{1}$ by applying the parity check matrix $H$ and changing the corresponding bit yields

Bob next forms a vector ${x}_{0}$ such that ${x}_{0}G={x}_{1}$, which can be done by extracting the first four components of ${x}_{1}$, that is,

Bob decrypts by calculating

which is the original plaintext message.

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.