Cryptology ePrint Archive: Report 2009/589

Information-set decoding for linear codes over Fq

Christiane Peters

Abstract: 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.

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)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]