Decoding Random Binary Linear Codes in $2^{n/20}$: How $1+1=0$ Improves Information Set Decoding

Anja Becker; Antoine Joux; Alexander May; Alexander Meurer

Paper 2012/026

Decoding Random Binary Linear Codes in $2^{n/20}$: How $1+1=0$ Improves Information Set Decoding

Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer

Abstract

Decoding random linear codes is a well studied problem with many applications in complexity theory and cryptography. The security of almost all coding and LPN/LWE-based schemes relies on the assumption that it is hard to decode random linear codes. Recently, there has been progress in improving the running time of the best decoding algorithms for binary random codes. The ball collision technique of Bernstein, Lange and Peters lowered the complexity of Stern's information set decoding algorithm to $2^{0.0556n}$. Using {\it representations} this bound was improved to $2^{0.0537n}$ by May, Meurer and Thomae. We show how to further increase the number of representations and propose a new information set decoding algorithm with running time $2^{0.0494n}$.

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. This is a full version of our same-named EUROCRYPT 2012 accepted paper
Keywords: Information Set Decoding Representation Technique
Contact author(s): alexander meurer @ rub de
History: 2012-01-20: received
Short URL: https://ia.cr/2012/026
License: CC BY

BibTeX

@misc{cryptoeprint:2012/026,
      author = {Anja Becker and Antoine Joux and Alexander May and Alexander Meurer},
      title = {Decoding Random Binary Linear Codes in $2^{n/20}$: How $1+1=0$ Improves Information Set Decoding},
      howpublished = {Cryptology ePrint Archive, Paper 2012/026},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/026}},
      url = {https://eprint.iacr.org/2012/026}
}