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

Leif Both; Alexander May

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.0953 n}$ is currently achieved via the BJMM-algorithm of Becker, Joux, May and Meurer. Our algorithm significantly improves this bound down to $2^{0.0885 n}$ . 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 cryptography Decoding binary linear codes BJMM Nearest Neighbors LPN Full Distance Decoding Representations
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: 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},
      url = {https://eprint.iacr.org/2017/1139}
}