On Solving Lpn using BKW and Variants

Sonia Bogos; Florian Tramer; Serge Vaudenay

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: 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},
      url = {https://eprint.iacr.org/2015/049}
}