Paper 2015/049

On Solving Lpn using BKW and Variants

Sonia Bogos, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Cryptography and Communications Discrete Structures, Boolean Functions and Sequences
DOI
10.1007/s12095-015-0149-2
Contact author(s)
soniamihaela bogos @ epfl ch
History
2015-12-10: last of 3 revisions
2015-01-22: received
See all versions
Short URL
https://ia.cr/2015/049
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/049,
      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{https://eprint.iacr.org/2015/049}},
      url = {https://eprint.iacr.org/2015/049}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.