24.10 The McEliece Cryptosystem – Introduction to Cryptography with Coding Theory, 3rd Edition

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 (.5501024)3×1085 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, k) linear error correcting code C with d(C)=d. He chooses S to be a k×k matrix that is invertible mod 2 and lets P be an n×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

G1=SGP.

The matrix G1 is the public key for the cryptosystem. Bob keeps S, G, 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

yxG1+e(mod 2).

Bob decrypts y as follows:

  1. Calculate y1yP1. (Since P is a permutation matrix, e1=eP1 is still a binary string of weight t. We have y1xSG+e1.)

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

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

  4. Compute xx0S1.

The security of the system lies in the difficulty of decoding y1 to obtain x1. 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, 512, 101] Goppa code. The Goppa codes have parameters of the form n=2m, d=2t+1, k=nmt. For example, taking m=10 and t=50 yields the [1024, 524, 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

G=1000110010010100100110001111, 

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

m=(1, 0, 1, 1)

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

S=1001110101011110

and

P=0010000100000000001000000010000000101000000001000.

Using these, Bob generates the public encryption matrix

G1=0011010101001111000101010100.

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

e=(0, 1, 0, 0, 0, 0, 0).

Then

y=(0, 0, 0, 1, 1, 0, 0).

Bob decrypts by first calculating

y1=yP1=(0, 0, 1, 0, 0, 0, 1).

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

x1=(0, 0, 1, 0, 0, 1, 1).

Bob next forms a vector x0 such that x0G=x1, which can be done by extracting the first four components of x1, that is,

x0=(0, 0, 1, 0).

Bob decrypts by calculating

x=x0S1=(1, 0, 1, 1), 

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 G1 is rather large.