Description
The McEliece cryptosystem was proposed by R.McEliece in 1978. In its original version it is based on Goppa codes. Given a public key matrix G and a codeword c=mG+e, we reduce the problem of recovering the error vector e to the shortest lattice vector problem. Using Conway and Sloane’s “Construction A”, we construct a basis of a lattice, in which the norm of the shortest vector w.r.t. lp norm is equal to the lp norm of the error vector e for plog(t), where t is the weight of the error vector e. To find such shortest vector in our lattice we use the LLL and block basis reduction algorithms for the lp norm, which guarantee only an approximation of the length of the shortest lattice vector. Our tests show that this attack method provides no positive results for Goppa codes of length more than 127. Born in 1979 in Pleven (Bulgaria), she studied “Mathematics with Computer Science” from 2001 to 2007 at TUD (Darmstadt University of Technology) and works since 2007 as a researcher for the Fraunhofer Institute for Secure Information Technology (SIT) in Darmstadt.
