A new algorithm for finding minimum-weight words in large linear codes

Anne Canteaut

BP 105
78153 Le Chesnay Cedex, France

In Cryptography and Coding - 5th IMA Conference LNCS 1025, pages 205-212.
Springer-Verlag, 1995.


An algorithm for finding small-weight words in large linear codes is developed and a precise analysis of its complexity is given. It is in particular able to decode random [512,256,57]-linear binary codes in 9 hours on a DEC alpha computer. We improve with it the previously best known attacks on some public-key cryptosystems and identification schemes based on error-correcting codes: for example we reduce the work factor involved in breaking McEliece's cryptosystem, since our algorithm requires 2^{64} elementary operations that is 128 times less than Lee-Brickell's attack.