Subset sum at constant density below one ⇒ Decision subset sum
Statement
Let with for a constant , so that the density is . If subset sum is hard at constant density below one for this , that is, is one-way, then decision subset sum is hard for : is indistinguishable from for uniform — IN96.
Notes
- The converse holds for every with negligible: a search algorithm that succeeds with probability distinguishes with advantage at least , since a uniform is a subset sum with probability at most — standard.
- Search-to-decision reductions for knapsack functions over arbitrary finite abelian groups, with bounded rather than binary coefficients, generalize this result under additional conditions on the group and the input distribution — MM11b.