Paper 2021/962

Practically Solving LPN

Thom Wiggers and Simona Samardjiska

Abstract

The best algorithms for the Learning Parity with Noise (LPN) problem require sub-exponential time and memory. This often makes memory, and not time, the limiting factor for practical attacks, which seem to be out of reach even for relatively small parameters. In this paper, we try to bring the state-of-the-art in solving LPN closer to the practical realm. We improve upon the existing algorithms by modifying the Coded-BKW algorithm to work under various memory constrains. We correct and expand previous analysis and experimentally verify our findings. As a result we were able to mount practical attacks on the largest parameters reported to date using only $2^{39}$ bits of memory.

Note: Since previous eprint submission: fixed small formatting error

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. IEEE ISIT 2021
Keywords
lpncryptanalysiscomplexity analysis
Contact author(s)
thom @ thomwiggers nl
simonas @ ru nl
History
2021-08-03: revised
2021-07-22: received
See all versions
Short URL
https://ia.cr/2021/962
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/962,
      author = {Thom Wiggers and Simona Samardjiska},
      title = {Practically Solving LPN},
      howpublished = {Cryptology ePrint Archive, Paper 2021/962},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/962}},
      url = {https://eprint.iacr.org/2021/962}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.