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.
Accepted at IEEE ISIT 2021.
Part of this work originally appeared in my master’s thesis
Software
LPN cryptanalysis implementations
We have an efficient software implementation in Rust that allows to compose attacks on LPN. It is available from github.
Efficient LPN chain finding algorithm
We hope to make our implementation available soon — it requires a bit of cleanup. Contact us if you want earlier access.
Chains found by our algorithm
We need to document the output format before we make this available. Contact us if you want earlier access.
Thom Wiggers
Senior Cryptography Researcher
My research interests include (post-quantum) cryptography and protocols