EPFL

Algo+LMA

This shows you the differences between two versions of the page.

en:projects:details:phd02 [2010/09/13 16:30] 127.0.0.1 external edit |
en:projects:details:phd02 [2016/06/23 11:26] |
||
---|---|---|---|

Line 1: | Line 1: | ||

- | ---- dataentry project ---- | ||

- | title : Cryptography based on error correcting codes | ||

- | contactname: Prof. Amin Shokrollahi | ||

- | contactmail_mail: amin.shokrollahi@epfl.ch | ||

- | contacttel: 021 6937512 | ||

- | contactroom: BC 110 | ||

- | type : phd theses | ||

- | status : completed | ||

- | table : projects | ||

- | created_dt : 2003-01-01 | ||

- | taken_dt : | ||

- | completed_dt : 2007-01-01 | ||

- | by : Lorenz Minder | ||

- | output_media400 : en:projects:lorenz_thesis.pdf|Download Lorenz's Thesis | ||

- | ====== | ||

- | template:datatemplates:project | ||

- | ---- | ||

- | |||

- | === Abstract: === | ||

- | 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. | ||

- | |||