Improvements of the attacks on cryptosystems based on error-correcting codes
INRIA, projet CODES
78153 Le Chesnay Cedex, France
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.