Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Generalized McEliece cryptosystemsecurity analysisStern attacklinear codes over Fqinformation-set decoding.
Contact author(s)
c p peters @ tue nl
History
2010-03-01: last of 3 revisions
2009-12-04: received
See all versions
Short URL
https://ia.cr/2009/589
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/589,
      author = {Christiane Peters},
      title = {Information-set decoding for linear codes over Fq},
      howpublished = {Cryptology ePrint Archive, Paper 2009/589},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/589}},
      url = {https://eprint.iacr.org/2009/589}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.