Paper 2015/049

On Solving Lpn using BKW and Variants

Sonia Bogos, Florian Tramer, and Serge Vaudenay


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.Cryptography and Communications Discrete Structures, Boolean Functions and Sequences
Contact author(s)
soniamihaela bogos @ epfl ch
2015-12-10: last of 3 revisions
2015-01-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sonia Bogos and Florian Tramer and Serge Vaudenay},
      title = {On Solving Lpn using BKW and Variants},
      howpublished = {Cryptology ePrint Archive, Paper 2015/049},
      year = {2015},
      doi = {10.1007/s12095-015-0149-2},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.