On iterative collision search for LPN and subset sum

Srinivas Devadas, Ling Ren, Hanshen Xiao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 15th International Conference, TCC 2017, Proceedings
EditorsYael Kalai, Leonid Reyzin
PublisherSpringer-Verlag
Pages729-746
Number of pages18
ISBN (Print)9783319705026
DOIs
StatePublished - Jan 1 2017
Externally publishedYes
Event15th International Conference on Theory of Cryptography, TCC 2017 - Baltimore, United States
Duration: Nov 12 2017Nov 15 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10678 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th International Conference on Theory of Cryptography, TCC 2017
CountryUnited States
CityBaltimore
Period11/12/1711/15/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On iterative collision search for LPN and subset sum'. Together they form a unique fingerprint.

Cite this