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:
Calculate . (Since is a permutation matrix, is still a binary string of weight . We have .)
Apply the error decoder for the code to to correct the “error” and obtain the codeword closest to .
Compute such that (in the examples we have considered, is simply the first bits of ).
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.
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.