Subset sum

The subset sum assumption states that, given uniformly random elements of and the sum modulo of a uniformly random subset of them, no efficient algorithm finds a subset with that sum.

Assumption

The assumption is parameterized by the number of elements , which also serves as the security parameter, and a modulus . The density of an instance is . For and write . Hardness of the search game below is one-wayness of the function (Subset sum ⇒ OWF), the form in which IN96 state it, with .

For the difference has a coefficient , so it is uniform over for uniform and is a universal hash family. At density the planted is therefore the only solution except with probability at most ; at the expected number of solutions, , exceeds , and for the pair is statistically close to uniform by the leftover hash lemma — standard.

Search subset sum

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{ss}}_{n,M,\calA}(\secpar)$}
\begin{algorithmic}
\State $\mathbf{a} \getsr \ZZ_M^n$; $\mathbf{s} \getsr \bits^n$
\State $t := \langle \mathbf{a}, \mathbf{s} \rangle$
\State $\mathbf{s}' \gets \calA(1^\secpar, \mathbf{a}, t)$
\Return $[\mathbf{s}' \in \bits^n \wedge \langle \mathbf{a}, \mathbf{s}' \rangle = t]$
\end{algorithmic}
\end{algorithm}

Subset sum is hard for if for all efficient ,

is negligible. The adversary wins with any solution, not only the planted one.

Decision subset sum

The decision variant asks to distinguish from for uniform .

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{dss}}_{n,M,\calA}(\secpar)$}
\begin{algorithmic}
\State $\mathbf{a} \getsr \ZZ_M^n$; $\mathbf{s} \getsr \bits^n$; $b \getsr \bits$
\State $t_0 := \langle \mathbf{a}, \mathbf{s} \rangle$; $t_1 \getsr \ZZ_M$
\State $b' \gets \calA(1^\secpar, \mathbf{a}, t_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

Decision subset sum is hard for if for all efficient ,

is negligible. For with , hardness of decision subset sum says that is a PRG with seed and stretch — standard.

Known Results

Worst-case hardness

Deciding whether some subset of given positive integers sums exactly to a given integer is NP-complete — Kar72. The cryptographic assumption concerns random modular instances.

Search–decision equivalence

Hardness of search subset sum at constant density below one, with and for a constant , implies hardness of decision subset sum for the same — IN96 (Subset sum at constant density below one ⇒ Decision subset sum). The converse holds whenever is negligible: run the search algorithm and check its answer, since a uniform has a solution with probability at most — standard. Once the decision problem is statistically hard, so the equivalence is meaningful only below density — standard.

Constructions

Variations

Subset sum at constant density below one

Subset sum is hard at constant density below one if, for a constant , subset sum is hard for with and , a density . This is the regime of the PRG and search-to-decision theorems of IN96.

Decision subset sum at constant density below one

Decision subset sum is hard at constant density below one if, for a constant , decision subset sum is hard for with and . This is the conclusion of the search-to-decision theorem of IN96.

Subset sum at constant density above one

Subset sum is hard at constant density above one if, for a constant , subset sum is hard for with and , a density . This is the regime of the UOWHF theorem of IN96.

Subset sum at the LPS10 parameters

Subset sum is hard at the LPS10 parameters if subset sum is hard for with the modulus of the LPS10 constructions. The parameters of the LPS10 encryption scheme satisfy , a density — KF15.

Attacks

  • Exhaustive and dynamic-programming algorithms. Dynamic programming over the reachable partial sums takes time , so must be superpolynomial in ; listing the sums of each half of the elements and matching them takes time and space — standard. Every instance can be solved in time and space — SS81.
  • Representations, at density close to . Writing the solution as a sum of two vectors in many ways gives heuristic algorithms for almost all instances of density : HGJ10 state running time , and BCJ11 give that algorithm as time with memory and lower the time to .
  • Lattice attacks, at low density. Lagarias and Odlyzko reduce subset sum to finding a shortest nonzero vector in a lattice built from — LO83. With an oracle for shortest vectors their algorithm solves almost all instances of density below in polynomial time, and either of two modified lattices raises the threshold to ; combined with lattice basis reduction in place of the oracle, the modifications also improve the attack in practice — CJL+92.
  • Subexponential algorithms at vanishing density. A BKW-style algorithm solves random instances of density in subexponential time; the parameters of the LPS10 encryption scheme, with , fall in time — KF15.
  • Merkle–Hellman. The Merkle–Hellman knapsack cryptosystem publishes a superincreasing sequence disguised by a modular multiplication — MH78. Shamir’s polynomial-time algorithm breaks the basic, singly iterated scheme — Sha82. The attack exploits the trapdoor structure of the public weights and does not apply to random instances — standard.

Participates in

Builds on Subset sum

Produces Subset sum