A new algorithm for finding minimum-weight words in a linear code: application to McEliece's cryptosystem and to 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 International Symposium on Information Theory, ISIT'97, page 327, 1997.

Abstract

An algorithm for finding minimum-weight words in large linear codes is developed. It notably points out that the original McEliece cryptosystem is not secure. We also determine with it the minimum distance of some BCH codes of length 511.