Solving LPN Using Covering Codes
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,18) LPN instance with complexity less than 2 80 operations in expec