TY - GEN
T1 - On iterative collision search for LPN and subset sum
AU - Devadas, Srinivas
AU - Ren, Ling
AU - Xiao, Hanshen
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85033776913&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85033776913&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-70503-3_24
DO - 10.1007/978-3-319-70503-3_24
M3 - Conference contribution
AN - SCOPUS:85033776913
SN - 9783319705026
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 729
EP - 746
BT - Theory of Cryptography - 15th International Conference, TCC 2017, Proceedings
A2 - Kalai, Yael
A2 - Reyzin, Leonid
PB - Springer
T2 - 15th International Conference on Theory of Cryptography, TCC 2017
Y2 - 12 November 2017 through 15 November 2017
ER -