Welcome to the resource topic for 2016/275
Title:
Faster Algorithms for Solving LPN
Authors: Bin Zhang, Lin Jiao, 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.
ePrint: https://eprint.iacr.org/2016/275
Talk: https://www.youtube.com/watch?v=x6-OR56dPSU
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .