Solving LPN Using Covering Codes
(2014) 20th Annual International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt) 8873. p.1-20- 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 instances suggested for 80-bit security in cryptographic schemes like HB variants, LPN-C and Lapin, in less than 2(80) operations.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/4926891
- author
- Guo, Qian
LU
; Johansson, Thomas
LU
and Löndahl, Carl LU
- organization
- publishing date
- 2014
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Advances in Cryptology - Asiacrypt 2014
- editor
- Iwata, Tetsu and Sarkar, Palash
- volume
- 8873
- pages
- 1 - 20
- publisher
- Springer
- conference name
- 20th Annual International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt)
- conference location
- Kaohsiung, Taiwan
- conference dates
- 2014-12-07 - 2014-12-11
- external identifiers
-
- wos:000354875800001
- scopus:84916641241
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 978-3-662-45610-1
- DOI
- 10.1007/978-3-662-45611-8_1
- language
- English
- LU publication?
- yes
- id
- 3927ad9d-9755-4a1e-a233-d32c88c92401 (old id 4926891)
- date added to LUP
- 2016-04-01 10:10:21
- date last changed
- 2025-01-14 07:49:37
@inproceedings{3927ad9d-9755-4a1e-a233-d32c88c92401, 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 instances suggested for 80-bit security in cryptographic schemes like HB variants, LPN-C and Lapin, in less than 2(80) operations.}}, author = {{Guo, Qian and Johansson, Thomas and Löndahl, Carl}}, booktitle = {{Advances in Cryptology - Asiacrypt 2014}}, editor = {{Iwata, Tetsu and Sarkar, Palash}}, isbn = {{978-3-662-45610-1}}, issn = {{1611-3349}}, language = {{eng}}, pages = {{1--20}}, publisher = {{Springer}}, title = {{Solving LPN Using Covering Codes}}, url = {{http://dx.doi.org/10.1007/978-3-662-45611-8_1}}, doi = {{10.1007/978-3-662-45611-8_1}}, volume = {{8873}}, year = {{2014}}, }