International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Solving LPN Using Covering Codes

Authors:
Qian Guo
Thomas Johansson
Carl Löndahl
Download:
DOI: 10.1007/s00145-019-09338-8
Search ePrint
Search Google
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 , 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.
BibTeX
@article{jofc-2020-30113,
  title={Solving LPN Using Covering Codes},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={33},
  pages={1-33},
  doi={10.1007/s00145-019-09338-8},
  author={Qian Guo and Thomas Johansson and Carl Löndahl},
  year=2020
}