Paper 2017/1139

Decoding Linear Codes with High Error Rate and its Impact for LPN Security

Leif Both and Alexander May


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.

Note: minor changes, notation

Available format(s)
Publication info
Preprint. Minor revision.
public-key cryptographyDecoding binary linear codesBJMMNearest NeighborsLPNFull Distance DecodingRepresentations
Contact author(s)
leif both @ rub de
2018-01-31: last of 2 revisions
2017-11-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Leif Both and Alexander May},
      title = {Decoding Linear Codes with High Error Rate and its Impact for LPN Security},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1139},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.