Classical algorithm techniques for decoding generic linear codes

Abstract : The security of code-based cryptosystems relies heavily on the hardness of decoding in an arbitrary linear code. The problem only has exponential solutions in the classical computing model, and it seems that it remains the case with quantum computing, placing code-based crypto among the so-called post-quantum cryptographic techniques. Even though quantum computer are not likely to allow generic decoding techniques with non-exponential complexity, it still allows some significant improvements. A few works have already explore this path. The purpose of this survey is not to propose new decoding techniques taking advantage a quantum computing. Instead we intend to give a comprehensive description of the main decoding techniques. The best techniques are recent (2011 and 2012) and are in fact finely tuned trade-offs between several very basic techniques. We will come back to those basics, which are the birthday decoding (based on the birthday paradox), and the Prange or Lee & Brickell algorithms (which are essentially enumerations). We feel that understanding each of those techniques in a quantum setting will simplify the search of an optimal quantum algorithm, and, hopefully, provide a simpler approach than directly "quantumize" the best known decoding techniques.
Type de document :
Communication dans un congrès
Dagstuhl Seminar 13371, Quantum Cryptanalysis, Sep 2013, Dagstuhl, Germany. 2013
Liste complète des métadonnées

https://hal.inria.fr/hal-00864837
Contributeur : Nicolas Sendrier <>
Soumis le : lundi 23 septembre 2013 - 13:17:06
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

  • HAL Id : hal-00864837, version 1

Collections

Citation

Nicolas Sendrier. Classical algorithm techniques for decoding generic linear codes. Dagstuhl Seminar 13371, Quantum Cryptanalysis, Sep 2013, Dagstuhl, Germany. 2013. 〈hal-00864837〉

Partager

Métriques

Consultations de la notice

217