Information-set decoding for linear codes over Fq

C.P. Peters

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

80 Citations (Scopus)


The best known non-structural attacks against code-based cryptosystems are based on 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 F_2. This paper presents a generalization of Stern's information-set-decoding algorithm for decoding linear codes over arbitrary finite fields F_q 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 F_31 are suggested for which the new information-set-decoding algorithm needs 2^128 bit operations.
Original languageEnglish
Title of host publicationPost-Quantum Cryptography (3rd International Workshop, PQCrypto 2010, Darmstadt, Germany, May 25-28, 2010)
EditorsN. Sendrier
Place of PublicationBerlin
ISBN (Print)978-3-642-12928-5
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Information-set decoding for linear codes over Fq'. Together they form a unique fingerprint.

Cite this