Paper 2017/904

On Iterative Collision Search for LPN and Subset Sum

Srinivas Devadas, Ling Ren, and Hanshen Xiao

Abstract

Iterative collision search procedures play a key role in developing combinatorial algorithms for the subset sum and learning parity with noise (LPN) problems. In both scenarios, the single-list pair-wise iterative collision search finds the most solutions and offers the best efficiency. However, due to its complex probabilistic structure, no rigorous analysis for it appears to be available to the best of our knowledge. As a result, theoretical works often resort to overly constrained and sub-optimal iterative collision search variants in exchange for analytic simplicity. In this paper, we present rigorous analysis for the single-list pair-wise iterative collision search method and its applications in subset sum and LPN. In the LPN literature, the method is known as the LF2 heuristic. Besides LF2, we also present rigorous analysis of other LPN solving heuristics and show that they work well when combined with LF2. Putting it together, we significantly narrow the gap between theoretical and heuristic algorithms for LPN.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCC 2017
Contact author(s)
renling @ mit edu
History
2017-09-28: revised
2017-09-24: received
See all versions
Short URL
https://ia.cr/2017/904
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/904,
      author = {Srinivas Devadas and Ling Ren and Hanshen Xiao},
      title = {On Iterative Collision Search for LPN and Subset Sum},
      howpublished = {Cryptology ePrint Archive, Paper 2017/904},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/904}},
      url = {https://eprint.iacr.org/2017/904}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.