Cryptology ePrint Archive: Report 2015/049

On Solving Lpn using BKW and Variants

Sonia Bogos and Florian Tramer and Serge Vaudenay

Abstract: The Learning Parity with Noise problem (LPN) is appealing in cryptography as it is considered to remain hard in the post-quantum world. It is also a good candidate for lightweight devices due to its simplicity. In this paper we provide a comprehensive analysis of the existing LPN solving algorithms, both for the general case and for the sparse secret scenario. In practice, the LPN-based cryptographic constructions use as a reference the security parameters proposed by Levieil and Fouque. But, for these parameters, there remains a gap between the theoretical analysis and the practical complexities of the algorithms we consider. The new theoretical analysis in this paper provides tighter bounds on the complexity of LPN solving algorithms and narrows this gap between theory and practice. We show that for a sparse secret there is another algorithm that outperforms BKW and its variants. Following from our results, we further propose practical parameters for different security levels.

Category / Keywords: public-key cryptography /

Date: received 21 Jan 2015, last revised 30 Jan 2015

Contact author: soniamihaela bogos at epfl ch

Available format(s): PDF | BibTeX Citation

Version: 20150130:125424 (All versions of this report)

Short URL: ia.cr/2015/049

Discussion forum: Show discussion | Start new discussion