"Subexponential algorithm for the subset-sum problem"
Paul Kirchner
(ENS Paris)
Monday, April 27th, 2015, 2:00 pm
EBU3B, Room 4258
Abstract:
We study the low-density randomized subset-sum problem, where given n uniform integers between 0 and 2^(nd), and the sum of any subset, the goal is to recover the subset. d=o(1) is called the density and we will show how to solve the problem in subexponential time 2^(n/(2-o(1))/ln(1/d)), while lattice reduction based achieve a complexity of 2^O(nd log(nd)).
The first step is to remark that we can embed the problem in a bounded distance decoding problem over a lattice, where the decoded point is in the fundamental parallelepiped of a known matrix.
The second step is a reduction of this problem into a learning with errors problem with binary secret (Binary-LWE).
The final step, our contribution, is to show a subexponential algorithm for this problem. The algorithm is a modification of the algorithm of Blum, Kalai, Wasserman, where we partially reduce each chunk (of variable size) of the vectors.
This result has a lot of cryptographic applications (e.g. NTRU, BLISS, public-key cryptosystems based on LWE) and also gives the first subexponential algorithm for restricted classical problems with polynomial approximation factors (GapSVP, UniqueSVP, BDD).