Improvements of the attacks on cryptosystems based on error-correcting codes
Anne Canteaut
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France Anne.Canteaut@inria.fr
Florent Chabaud
LIENS
45, rue d'Ulm
75230 Paris Cedex 05, France Florent.Chabaud@ens.fr
Research Report LIENS-95-21, École Normale Supérieure, Paris, July 1995.
Abstract
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.