Solving LPN Using Covering Codes
Peer reviewed, Journal article
Published version
Åpne
Permanent lenke
https://hdl.handle.net/1956/22601Utgivelsesdato
2019-10-15Metadata
Vis full innførselSamlinger
Originalversjon
https://doi.org/10.1007/s00145-019-09338-8Sammendrag
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,1/8) LPN instance with complexity less than 2^80 operations in expectation, indicating that cryptographic schemes like HB variants and LPN-C should increase their parameter size for 80-bit security.