Information-Set Decoding for Linear Codes over F-q

Christiane Peters

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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 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 cryptosysterns using classical Goppa codes over F-31 are suggested for which the new information-set-decoding algorithm needs 2(128) bit operations.
Keyword: MCELIECE CRYPTOSYSTEM,TELECOMMUNICATIONS,Stern attack,Generalized McEliece cryptosystem,information-set decoding,COMPUTER,linear codes over F-q,security analysis,ALGORITHM,LENGTH
Original languageEnglish
Title of host publicationPROCEEDINGS OF POST-QUANTUM CRYPTOGRAPHY
VolumeVolume 6061
Place of PublicationBERLIN
PublisherSpringer Verlag
Publication date2010
Pages81-94
ISBN (Print)978-36-42-12928-5
Publication statusPublished - 2010
Externally publishedYes
EventInternational Workshop on Post-Quantum Cryptography -
Duration: 1 Jan 2010 → …
Conference number: 3

Conference

ConferenceInternational Workshop on Post-Quantum Cryptography
Number3
Period01/01/2010 → …

Fingerprint Dive into the research topics of 'Information-Set Decoding for Linear Codes over F-q'. Together they form a unique fingerprint.

Cite this