Abstract We present a new algorithm for solving the LPN problem. The algorithm has a similar form as some previous methods, but includes a new key step that makes use of approximations of random words to a nearest codeword in a linear code. It outperforms previous methods for many parameter choices. In particular, we can now solve the $$(512,\frac{1}{8})$$ (512,18) LPN instance with complexity less than $$2^{80}$$ 280 operations in expectation, indicating that cryptographic schemes like HB variants and LPN-C should increase their parameter size for 80-bit security.

The learning parity with noise (LPN) problem has recently proved to be of great importance in cryptology. A special and very useful case is the Ring-LPN problem, which typically provides improved efficiency in the constructed cryptographic primitive. We present a new algorithm for solving the Ring-LPN problem in the case when the polynomial used is reducible. It greatly outperforms the previous algorithms for solving this problem. Using the algorithm, we can break the Lapin authentication protocol for the proposed instance using a reducible polynomial, in ~271bit operations.