A new algorithm for finding minimum-weight words in a linear code: application to primitive narrow-sense BCH codes of length 511


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

IEEE Transactions on Information Theory , 44(1):367-378, 1998.

Abstract

An algorithm for finding minimum-weight words in large linear codes is developed. It improves all previous attacks on the public-key cryptosystems based on codes and it notably points out some weaknesses in McEliece's cipher. We also determine with it the minimum distance of some BCH codes of length~511.

Keywords

error-correcting codes, decoding algorithm, minimum weight, McEliece's cryptosystem, BCH codes.