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

Link to this comparison view

en:projects:details:phd02 [2010/11/16 12:02]
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 thesis 
-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 
-=== 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.