International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 11 March 2016

Bin Zhang, Lin Jiao, Mingsheng Wang
ePrint Report ePrint Report
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.
Expand

Additional news items may be found on the IACR news page.