# 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  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  to be the generating matrix for an  linear error correcting code  with . He chooses  to be a  matrix that is invertible mod 2 and lets  be an  permutation matrix, which means that  has exactly one 1 in every row and in every column, with all the other entries being 0. Define



The matrix  is the public key for the cryptosystem. Bob keeps  secret.

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



Bob decrypts  as follows:

1. Calculate . (Since  is a permutation matrix,  is still a binary string of weight . We have .)

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

3. Compute  such that  (in the examples we have considered,  is simply the first  bits of ).

4. Compute .

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

To make decoding difficult,  should be chosen to be large. McEliece suggested using a  Goppa code. The Goppa codes have parameters of the form . For example, taking  and  yields the  code just mentioned. It can correct up to 50 errors. For given values of  and , 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  Hamming code. Suppose Alice wishes to send a message



to Bob. In order to do so, Bob must create an invertible matrix  and a random permutation matrix  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  and calculates the ciphertext . In the case of a Hamming code the error vector has weight . Suppose Alice chooses



Then



Bob decrypts by first calculating



Calculating the syndrome of  by applying the parity check matrix  and changing the corresponding bit yields



Bob next forms a vector  such that , which can be done by extracting the first four components of , 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  is rather large.