Welcome to the resource topic for 2017/780
Title:
New Algorithms for Solving LPN
Authors: Bin Zhang, 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.
ePrint: https://eprint.iacr.org/2017/780
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .