Subset sum at constant density below one ⇒ Decision subset sum

Standard model · IN96

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.