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
-
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}
}
