Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas
Contributor : Nicolas Sendrier <>
Submitted on : Monday, September 23, 2013 - 1:17:06 PM
Last modification on : Friday, May 25, 2018 - 12:02:05 PM


  • HAL Id : hal-00864837, version 1



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



Record views