International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Carl Löndahl

Publications

Year
Venue
Title
2020
JOFC
Solving LPN Using Covering Codes
Qian Guo Thomas Johansson Carl Löndahl
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 , 1 8 ) LPN instance with complexity less than $$2^{80}$$ 2 80 operations in expectation, indicating that cryptographic schemes like HB variants and LPN-C should increase their parameter size for 80-bit security.
2014
ASIACRYPT

Coauthors

Qian Guo (2)
Thomas Johansson (2)
Carl Löndahl (2)