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
LPNBKWPerfect codeHBLapin
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2016/275}},
      url = {https://eprint.iacr.org/2016/275}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.