[Resource Topic] 2009/589: Information-set decoding for linear codes over Fq

Welcome to the resource topic for 2009/589

Information-set decoding for linear codes over Fq

Authors: Christiane Peters


A code-based cryptosystem is considered secure if the best known attack against it is information-set decoding. Stern’s algorithm and its improvements are well optimized and the complexity is reasonably well understood. However, these algorithms only handle codes over F2. This paper presents a generalization of Stern’s information-set-decoding algorithm for decoding linear codes over arbitrary finite fields Fq and analyzes the complexity. This result makes it possible to compute the security of recently proposed code-based systems over non-binary fields. As an illustration, ranges of parameters for generalized McEliece cryptosystems using classical Goppa codes over F31 are suggested for which the new information-set-decoding algorithm needs 2^128 bit operations.

ePrint: https://eprint.iacr.org/2009/589

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .