Welcome to the resource topic for 2012/026
Title:
Decoding Random Binary Linear Codes in 2^{n/20}: How 1+1=0 Improves Information Set Decoding
Authors: Anja Becker, Antoine Joux, Alexander May, 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}.
ePrint: https://eprint.iacr.org/2012/026
Talk: https://www.youtube.com/watch?v=46BdaS3GbcA
Slides: https://iacr.org/cryptodb/archive/2012/EUROCRYPT/presentation/24271.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .