Paper 2017/1139

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

Leif Both and 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.

Note: minor changes, notation

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

BibTeX

@misc{cryptoeprint:2017/1139,
      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{https://eprint.iacr.org/2017/1139}},
      url = {https://eprint.iacr.org/2017/1139}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.