Title :
A new algorithm for finding minimum-weight words in a linear code: application to McEliece´s cryptosystem and to narrow-sense BCH codes of length 511
Author :
Canteaut, Anne ; Chabaud, Florent
Author_Institution :
Projet Codes, Inst. Nat. de Recherche en Inf. et Autom., Le Chesnay, France
fDate :
1/1/1998 12:00:00 AM
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 (1978) cipher. We also determine with it the minimum distance of some BCH codes of length 511
Keywords :
BCH codes; binary sequences; computational complexity; decoding; linear codes; public key cryptography; Markov chain; McEliece´s cipher; McEliece´s cryptosystem; NP-complete problem; code length; decoding algorithm; error correcting codes; linear binary code; minimum-weight words; narrow-sense BCH codes; public-key cryptosystems; Binary codes; Decoding; Error correction codes; Iterative algorithms; Linear code; NP-complete problem; Polynomials; Public key; Public key cryptography; Security;
Journal_Title :
Information Theory, IEEE Transactions on
