Cryptography based on error correcting codes

The idea to use error-correcting codes in order to construct public key cryptosystems was published in 1978 by McEliece [ME1978]. In his original construction, McEliece used Goppa codes, but various later publications suggested the use of different families of error-correcting codes. The choice of the code has a crucial impact on the security of this type of cryptosystem. Some codes have a structure that can be recovered in polynomial time, thus breaking the cryptosystem completely, while other codes have resisted attempts to cryptanalyze them for a very long time now. In this thesis, we examine different derivatives of the McEliece cryptosystem and study their structural weaknesses. The main results are the following: In chapter 3 we devise an effective structural attack against the McEliece cryptosystem based on algebraic geometry codes defined over elliptic curves. This attack is inspired by an algorithm due to Sidelnikov and Shestakov [SS1992] which solves the corresponding problem for Reed-Solomon codes. The presented algorithm is heuristic polynomial time and thus inverts trapdoors even for very large codes. In chapter 4, we show that the Sidelnikov cryptosystem [S1994], which is based on binary Reed-Muller codes, is insecure. The basic idea of our attack is to use the fact that minimum weight words in a Reed-Muller code have very particular properties. This attack relies on the ability to find minimum weight words in the code, a problem that is, in this specific instance, much easier than general decoding, and feasible for interesting parameters in a modest amount of time. The attack has subexponential running time if the order of the code is kept fixed, and it breaks the large keys as proposed by Sidelnikov in under an hour on a stock PC. In the chapter 5, we finally discuss some of the problems to solve if one attempts to generalize these algorithms.