This project has been written under the subject coding theory and takes its focus on the McEliece cryptosystem. The main disadvantage of this cryptosystem is the large public key size and therefore we have researched the possibility of reducing it by using matrix-product codes. In the first chapter, we present the McEliece cryptosystem and also McEliece’s original proposal to use Goppa codes for the cryptosystem. We also consider the equivalent cryptosystem developed by Nieddereiter and thus a comparison of these two cryptosystems is given. From here, we only focus on the McEliece cryptosystem due to the fact that these
cryptosystems are equivalent. Chapter two considers two kinds of attacks on the cryptosystem namely message attack and key attack. These attacks have been used against the McEliece cryptosystem with different families of codes. In this chapter it is shown through examples that breaking the McEliece cryptosystem is very expensive even for small parameters of the code. It is further noted that some types of codes are still secure meaning that they can resist known attacks. One of these types are irreducible binary Goppa codes. We aim to reduce the public key size in the cryptosystem and one way of doing this is by looking at codes that have a quasi cyclic structure. Therefore the theory of these codes is presented in chapter three. Also in this chapter we introduce Gaborit’s version of the McEliece cryptosystem. This version uses the quasi cyclic structure and a special way of generating the generator matrix to reduce the public key size in the McEliecce cryptosystem. Furthermore, he changes the key generating algorithm in such a way that the generator matrix is now only hidden by a permutation matrix. In Gaborit’s version he uses subcodes of known BCH-codes, and by using this it has been shown that the system can be broken. Even though, the version has been broken, the main idea can be used to develop a new version of the McEliece cryptosystem using matrix-product codes. In chapter four, we present exactly this type of codes. Among others it is shown, that the minimum distance of these codes can be calculated exactly under given conditions. Moreover, a decoding algorithm for matrix-product codes is given, when the codes are nested and the matrix is non-singular by columns. Another example of using this type of codes in the McEliece cryptosystem is provided. A new version of the McEliece cryptosystem is presented in chapter five. This version uses matrix-product codes, and Gaborit’s idea of finding a permutation in such a way, that the permutations only are within the small parts of the codeword. Furthermore the new version uses the fact that chapter four showed that a generator matrix for a matrixproduct code can be constructed from the small codes generator matrices and the matrix A. Knowing this it is now possible to reduce the public key size of the McEliece cryptosystem by only sending these relatively small generator matrices and matrix A in stead of a very large generator matrix for the entire matrix-product code. When Gaborit’s idea is used for the new version of the McEliece cryptosystem, one might think that the new version such as Gaborit’s can be broken. It is suggested, that if irreducible binary nested Goppa codes are used it might not be possible to break the version, since this is one of the code types that are still secure against attacks. Furthermore, it is stated that for future work it might be interesting to look at subfield subcodes and use this family of codes for the new version. This idea is also proposed by Berger for Gaborit’s version of the McEliece cryptosystem.