Practically Solving LPN
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 239 bits of memory.
Type
Publication
IEEE International Symposium on Information Theory 2021
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.
Authors
Senior Cryptography Researcher
Thom Wiggers is a cryptography researcher at PQShield.
His PhD thesis was on the interactions of post-quantum cryptography with protocols, under the supervision of Peter Schwabe, at the Institute of Computing and Information Sciences, Radboud University in The Netherlands.
Authors