Ms Naomi Benger

Honours thesis

The polynomial reconstruction problem

The use of cryptography has been traced back as early as the Roman times, when Caesar used a simple shift cipher to disguise messages. Since then there have been a lot of advances in mathematics and, in particular most recently, in computers. The need for security of information has grown, as has the ability to compute more complicated algorithms and also, very importantly, the ability to decipher messages. We are now, with the aid of computers, able to compute complicated algorithms which, even as recently as 50 years ago, would have been impossible. With such rapid development in technology, it is important that the algorithms are constantly updated, in order to keep up with the improvements in computers and advancing knowledge. One of the most important areas of research in cryptography is devising new hard problems on which to base a cryptosystem. Once a problem has been developed and deemed suitably hard, it is then a nontrivial task to construct a cryptosystem around that problem. The Polynomial Reconstruction Problem (also known as the Reed-Solomon decoding problem) was introduced in 1999 and in 2002 was deemed a suitably hard problem for the basis of a cryptosystem [KY02]. Since then a private key cryptosystem has been developed; although the hardness property seemed to be well used in this cryptosystem, it has fallen to attacks that do not target solving the polynomial reconstruction problem itself, but exploit other aspects of the encryption algorithm of the system. This pro ject examines the polynomial reconstruction problem and how it has been used in cryptography. A brief introduction to the concepts of coding and cryptology is followed by an introduction of polynomial interpolation, a method used in the decryption stages of the cryptosystem and modi?cations of the cryptosystem to be discussed later. After this an introduction to Reed-Solomon codes and the Reed-Solomon decoding problem is presented in chapter 5. Then the Polynomial Reconstruction Problem and its relationship to the Reed-Solomon decoding problem is discussed. Finally the public key encryption system proposed by Augot and Finiasz is addressed, along with attacks on the system, modi?cations and subsequent attacks.