Classical algorithm techniques for decoding generic linear codes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Classical algorithm techniques for decoding generic linear codes

Résumé

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.
Fichier non déposé

Dates et versions

hal-00864837 , version 1 (23-09-2013)

Identifiants

  • HAL Id : hal-00864837 , version 1

Citer

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

Collections

INRIA INRIA2
127 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More