Welcome to the resource topic for 2017/1139
Title:
Decoding Linear Codes with High Error Rate and its Impact for LPN Security
Authors: Leif Both, Alexander May
Abstract:We propose a new algorithm for the decoding of random binary linear codes of dimension n that is superior to previous algorithms for high error rates. In the case of Full Distance decoding, the best known bound of 2^{0.0953n} is currently achieved via the BJMM-algorithm of Becker, Joux, May and Meurer. Our algorithm significantly improves this bound down to 2^{0.0885n}. Technically, our improvement comes from the heavy use of Nearest Neighbor techniques in all steps of the construction, whereas the BJMM-algorithm can only take advantage of Nearest Neighbor search in the last step. Since cryptographic instances of LPN usually work in the high error regime, our algorithm has implications for LPN security.
ePrint: https://eprint.iacr.org/2017/1139
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 .