Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography, Decoding binary linear codes, BJMM, Nearest Neighbors, LPN, Full Distance Decoding, Representations

Date: received 24 Nov 2017, last revised 31 Jan 2018

Contact author: leif both at rub de

Available format(s): PDF | BibTeX Citation

Note: minor changes, notation

Version: 20180131:113522 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]