You are looking at a specific version 20171127:132906 of this paper. See the latest version.

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.0886n}$. 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Decoding binary linear codesBJMMNearest NeighborsLPNFull Distance DecodingRepresentations
Contact author(s)
Alex may @ 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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.