Paper 2017/780

New Algorithms for Solving LPN

Bin Zhang and Xinxin Gong

Abstract

The intractability of solving the LPN problem serves as the security source of many lightweight/post-quantum cryptographic schemes proposed over the past decade. There are several algorithms available so far to fulfill the solving task. In this paper, we present further algorithmic improvements to the existing work. We describe the first efficient algorithm for the single-list $k$-sum problem which naturally arises from the various BKW reduction settings, propose the hybrid mode of BKW reduction and show how to compute the matrix multiplication in the Gaussian elimination step with flexible and reduced time/memory complexities. The new algorithms yield the best known tradeoffs on the %time/memory/data complexity curve and clearly compromise the $80$-bit security of the LPN instances suggested in cryptographic schemes. Practical experiments on reduced LPN instances verified our results.

Note: Parts of the work have been done when Bin Zhang has taken a visit in NTU, Singapore in 2016.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
LPNSingle-list $k$-sum problemGaussian eliminationTradeoffBKW.
Contact author(s)
gongxinxin} @ tca iscas ac cn
History
2017-08-16: received
Short URL
https://ia.cr/2017/780
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/780,
      author = {Bin Zhang and Xinxin Gong},
      title = {New Algorithms for Solving LPN},
      howpublished = {Cryptology ePrint Archive, Paper 2017/780},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/780}},
      url = {https://eprint.iacr.org/2017/780}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.