Cryptology ePrint Archive: Report 2016/275

Faster Algorithms for Solving LPN

Bin Zhang and 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.

Category / Keywords: LPN, BKW, Perfect code, HB, Lapin

Original Publication (with minor differences): IACR-EUROCRYPT-2016

Date: received 10 Mar 2016

Contact author: zhangbin at tca iscas ac cn, jiaolin at tca iscas ac cn

Available format(s): PDF | BibTeX Citation

Version: 20160311:103557 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]