Solving LPN Using Covering Codes
(2020) In Journal of Cryptology 33(1). p.1-33- 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,18) 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.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/504da419-cab7-4b6e-8d4f-62ed2b7e7e73
- author
- Guo, Qian LU ; Johansson, Thomas LU and Löndahl, Carl LU
- organization
- publishing date
- 2020-01
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- BKW, Covering codes, HB, Lapin, LPN, LPN-C
- in
- Journal of Cryptology
- volume
- 33
- issue
- 1
- pages
- 33 pages
- publisher
- Springer
- external identifiers
-
- scopus:85074455908
- ISSN
- 0933-2790
- DOI
- 10.1007/s00145-019-09338-8
- language
- English
- LU publication?
- yes
- id
- 504da419-cab7-4b6e-8d4f-62ed2b7e7e73
- date added to LUP
- 2019-11-22 11:59:15
- date last changed
- 2023-09-09 17:57:27
@article{504da419-cab7-4b6e-8d4f-62ed2b7e7e73, abstract = {{<p>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 <sup>80</sup> operations in expectation, indicating that cryptographic schemes like HB variants and LPN-C should increase their parameter size for 80-bit security.</p>}}, author = {{Guo, Qian and Johansson, Thomas and Löndahl, Carl}}, issn = {{0933-2790}}, keywords = {{BKW; Covering codes; HB; Lapin; LPN; LPN-C}}, language = {{eng}}, number = {{1}}, pages = {{1--33}}, publisher = {{Springer}}, series = {{Journal of Cryptology}}, title = {{Solving LPN Using Covering Codes}}, url = {{http://dx.doi.org/10.1007/s00145-019-09338-8}}, doi = {{10.1007/s00145-019-09338-8}}, volume = {{33}}, year = {{2020}}, }