Paper 2009/589 Original: eprint.iacr.org/2009/589 ↗
Information-set decoding for linear codes over Fq
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
- Preprint.
- History
- 2010-03-01: last updated
- 2009-12-04: published
- Short URL
- https://ia.cr/2009/589
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2009/589}
}