Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Solving LPN Using Covering Codes

Guo, Qian LU ; Johansson, Thomas LU orcid and Löndahl, Carl LU (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:
author
; and
organization
publishing date
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
2024-03-24 03:22:32
@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}},
}