Application to McEliece Public Key Cryptosystem

We follow section 1.2 of [CHA].

Here is a brief description of this cryptosystem. Alice is sending a message to Bob. Eve is trying to read Alice's message. Given is a $[n,k,d]$ binary code with generator matrix $G$ and also given is a decoding algorithm that corrects up to $t$ errors. As input parameters are an invertible $k\times k$ matrix $S$ and an $n\times n$ permutation matrix $P$. The triplet $(S,G,P)$ will be the secret key and the pair $(t,\hat{G}=SGP)$ will be the public key. Everyone knows the public key, but Alice and Bob are the only two who know the secret key. For Alice to transmit a $k$ bit message $m$, she sends the cipher text $c=m\hat{G}+e$, where $e$ is a random vector of weight at most $t$. To decipher the cipher text Bob decodes $cP^{-1}=mSG+eP^{-1}$ using the given algorithm.

To decrypt an encoded message, consider the matrix

$$G'=\left( \begin{array}{c} \hat{G}\\ m\hat{G}+e \end{array}\right) .$$

This is the generator matrix of a linear code $C'$ with minimum weight codeoword $e$. Note that $e$ is the only vector in $C'$ of minimum weight, by construction. Algorithm 3 can be modified to yield not only the minimum distance, but also a vector of minimum wieght. Using this fact Eve can solve for $e$, and therefore she can solve for the message $m$ sent by Alice. This example illustrates the usefulness of fast minimum distance algorithms for cracking certain types of McEliese cyrptosystems.