Hamming Codes and the McEliece Cryptosystem

Abstract

In this paper, we seek to understand some basic principles of coding theory. Specifically, we define and explore binary codes, Hamming codes, and a special application of coding theory known as the McEliece cryptosystem. We describe the meaning and usage of generator matrices and parity check matrices and present bounds on the number of codewords in codes of a given minimum distance and length. We present and prove several known results about Hamming codes, including the fact that they are necessarily perfect codes. We show how to construct a cryptosystem using any linear code and discuss the strength of the McEliece cryptosystem in a future where quantum computers are a reality. Finally, we present one program which automatically decodes strings encoded with a Hamming code and another which encrypts and decrypts messages using the McEliece cryptosystem.