Improvements of the attacks on cryptosystems based on error-correcting codes

Anne Canteaut

BP 105
78153 Le Chesnay Cedex, France

Florent Chabaud
45, rue d'Ulm
75230 Paris Cedex 05, France

Research Report LIENS-95-21, École Normale Supérieure, Paris, July 1995.


Many public-key cryptosystems and identification schemes based on error-correcting codes have been proposed as an alternative to the common cryptographic algorithms based on number theory. They rely on the NP-hardness of finding a fixed-weight word in a coset of a linear binary code. We here improve the previous attacks on these systems; this notably enables us to reduce the work factor involved in breaking McEliece's cryptosystem since our algorithm requires 264.2 operations that is 128 times less than Lee-Brickell's attack.


Error-correcting codes, Minimum weight codewords, Markov chains, McEliece's cryptosystem, Cryptanalysis.

Postscript version