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 (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:
author
; and
organization
publishing date
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}},
}