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 $2^{39}$ bits of memory.

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.

Thom Wiggers
Thom Wiggers
Senior Cryptography Researcher

My research interests include (post-quantum) cryptography and protocols