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.
Category / Keywords: public-key cryptography / Generalized McEliece cryptosystem, security analysis, Stern attack, linear codes over Fq, information-set decoding. Date: received 1 Dec 2009, last revised 1 Mar 2010 Contact author: c p peters at tue nl Available format(s): PDF | BibTeX Citation Version: 20100301:084511 (All versions of this report) Short URL: ia.cr/2009/589 Discussion forum: Show discussion | Start new discussion