Faster Algorithms for Solving LPN

Bin Zhang; Lin Jiao; Mingsheng Wang

Paper 2016/275

Faster Algorithms for Solving LPN

Bin Zhang, Lin Jiao, and Mingsheng Wang

Abstract

The LPN problem, lying at the core of many cryptographic constructions for lightweight and post-quantum cryptography, receives quite a lot attention recently. The best published algorithm for solving it at Asiacrypt 2014 improved the classical BKW algorithm by using covering codes, which claimed to marginally compromise the $80$-bit security of HB variants, LPN-C and Lapin. In this paper, we develop faster algorithms for solving LPN based on an optimal precise embedding of cascaded concrete perfect codes, in a similar framework but with many optimizations. Our algorithm outperforms the previous methods for the proposed parameter choices and distinctly break the 80-bit security bound of the instances suggested in cryptographic schemes like HB$^+$, HB$^\#$, LPN-C and Lapin.

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in EUROCRYPT 2016
Keywords: LPN BKW Perfect code HB Lapin
Contact author(s): zhangbin @ tca iscas ac cn
jiaolin @ tca iscas ac cn
History: 2016-03-11: received
Short URL: https://ia.cr/2016/275
License: CC BY

BibTeX

@misc{cryptoeprint:2016/275,
      author = {Bin Zhang and Lin Jiao and Mingsheng Wang},
      title = {Faster Algorithms for Solving {LPN}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/275},
      year = {2016},
      url = {https://eprint.iacr.org/2016/275}
}