Subset Sum from Lattice Reduction

Vadim's talk at 2nd BIU gives good intro to why we can use LLL for subset sum in theory, this note focus on "how exactly" in practice for the engineers, as my digest of various related work and why they make sense.

Here's the implementation of this SSP solver in python.

Recall that the goal of lattice reduction algorithms are to find orthonormal bases (i.e. nice, short, and nearly orthogonal) given an arbitrary bases of the lattice. More technically, they obtain a basis whose Gram-Schmidt vectors are not decreasing too quickly (which implies that the basis vectors are somewhat orthogonal to each other).

• Theorm^[1]: the vector
  ${\mathbf{b}}_1^{\prime }$ in a LLL-reduced basis (is short) has length at most
  $2^{(n-1)/2}\cdot {\lambda }_1(\mathcal{L}\mathcal{(}\mathbf{B}\mathcal{)})$

For now, we treat lattice reduction algorithm like LLL as an oracle that returns short bases in a lattice, and amazingly even finds the shortest non-zero vector in the lattice with high probability in polynomial time.

Recall the Subset Sum Problem (SSP):

• [SSP]: Given a multiset
  $\text{set}{a}_i$, and a target
  $S=\sum _{i=1}^n{a}_i\cdot x_i$ where
  $x_i\in \text{set}0,1$, find a subset that sums to
  $S$.
  • Brickell and Lagarias & Odlyzko showed that almost all low-density subset sum can be solved in poly time,
    $d=n/\log max{a}_i$ ;
    $d>1$ generally mean many subset solutions with the same target sum; we are interested in
    $d\le 1$.
  • SSP doesn’t constrain
    $|\mathbf{x}\mathbf{|}$ since it is tasked to find a solution, not “the” solution.

Utilizing LLL to solve SSP is essentially reducing the latter to the former, here’re some attempts that gradually build towards the one reduction that we’ll use. At the center, we need to construct a problem instance

$B^t=[{\mathbf{b}}_1|{\mathbf{b}}_2|\dots |{\mathbf{b}}_d]$, given the SSP set

$\text{set}{a}_i$, to feed into the LLL oracle such that the returned

${\mathbf{b}}_1^{\prime }$ from the reduced bases correspond to the SSP solutions.

• note:
  $d\le n$,
  $d$ is called lattice dimension,
  $n$ is called embedding dimension, most cases in cryptography, people consider squared, fully-ranked matrix. When we only use
  $n$ subscript, we are implicitly using full-rank
  $B$
• notation: by convention (and in python),
  $B$ is a row matrix, first row is
  $b_1$, but in lattice crypto, the convention is taking column matrix as input, which we denotes
  $B^t$

First Attempt

$$B=\left[\begin{array}{cc}\mathbf{I}& \mathbf{a}\\ \mathbf{0}& -S\end{array}\right]={\left[\begin{array}{cccccc}{b}_1:=& (1& 0& \dots & 0& a_1)\\ b_2:=& (0& 1& \dots & 0& a_2)\\ & & \dots & \\ b_n:=& (0& 0& \dots & 1& a_n)\\ b_{n+1}:=& (0& 0& \dots & 0& -S)\end{array}\right]}_{(n+1)\times (n+1)}$$

Now, any lattice point in

$\mathcal{L}(B^t)$ can be expressed by a linear combination of the row vectors. Let’s denote the linear combinator

$\text{set}{c}_i$:

$$z=[z_1,\dots ,z_{n+1}]=[c_1,c_2,\dots ,c_n,\sum _{i=1}^n{c}_i\cdot a_i-c_{n+1}\cdot S]\in \mathcal{L}(B^t)$$

It’s not hard to verify that actual solution

$\mathbf{x}\in \mathcal{L}$ is a short vector in the lattice, thus we can hope that our LLL oracle finds it, and we can check this condition on the reduced

$b_1^{\prime }$:

$z_i\in \text{set}0,1\text{for }i\in [n]\wedge z_{n+1}=0$, then output

$(z_i{)}_{i\in [n]}$ as the solution. Wola!

Unfortunately, there’s a problem: there could be shorter vectors than

$\mathbf{x}$ and lattice oracle might return them instead!

1. If any one of
   $a_i$ is small, then that row itself is already a short vector
2. if any two inputs are close
   $a_i\approx a_j$, then the difference (i.e.
   $ro{w}_i-ro{w}_j$) is a short vector
   1. more generally, if
      ${\beta }_i{a}_i\approx {\beta }_j{a}_j$ for any small integer coeffs
      ${\beta }_i,{\beta }_j$, then
      $z:=({\beta }_i\cdot ro{w}_i-{\beta }_j\cdot ro{w}_j)$ is a short vector

In short, all the above 3 cases presents high probability of our lattice oracle failing to produce the intended solution of SSP, and since we don’t have prior knowledge or constraint on values of

$\text{set}{a}_i$, we need to modify our

$B$ to avoid these possibilities.

Second Attempts

Both cases above can be solved with one simple trick: scale the last column with some value

$N>\sqrt{n}$ (don’t worry about the bound, just think a big number like 1000)!

$$B=\left[\begin{array}{cc}\mathbf{I}& N\mathbf{a}\\ \mathbf{0}& -NS\end{array}\right]={\left[\begin{array}{ccccc}1& 0& \dots & 0& N{a}_1\\ 0& 1& \dots & 0& N{a}_2\\ & & \dots & \\ 0& 0& \dots & 1& N{a}_n\\ 0& 0& \dots & 0& -NS\end{array}\right]}_{(n+1)\times (n+1)}$$

Each row is no longer a short vector, and LLL does need more work to find an actual smaller vector in this lattice. And the second concern is also mitigated since the delta

${\beta }_{i}N{a}_i-{\beta }_{j}N{a}_j$ is also scaled up, thus unlikely to be a shorter vector than our intended solution

$\mathbf{x}$ anymore.

• note: if
  $a_i=a_j$, then the second concern still stands, we will discuss this towards the end.

This version is essentially Lagarias and Odlyzko’s reduction in their work “Solving low-density subset sum problems”.

There are still some unsatisfactory limitations:

1. the success probability is bounded, and based on analysis in LO’85, this reduction only works for SSP with density

   $d<0.6463$ (another detailed analysis is in P.58 of LaMacchia’s “Basis Reduction Algorithms and Subset Sum Problems”)

2. observe the entry

   $z_{n+1}:=N(\sum _{i=1}^n{c}_i\cdot a_i-c_{n+1}\cdot S)$: what if
   $c_1{a}_1+c_2{a}_2=c_{n+1}\cdot S$ for some coefficients
   $c_1,c_2,c_{n+1}>1$? Then there are more competing short vectors again.

   (e.g.):

   $[0,0,2,0,1,0,0]$ v.s.
   $\mathbf{x}=[1,1,0,1,1,1,0]$ where
   $2a_3+a_5=5S$ and
   $a_1+a_2+a_4+a_5+a_6=S$. the former is a shorter vector and more likely to be returned by LLL oracle, but not exactly what we wanted.

In short, the lesson is we want to add even more constraints to the coefficients

$\text{set}{c}_i$ that contributes to the term

$z_{n+1}$ so that constraining

$z_{n+1}=0$ actually leads to

$(z_i{)}_{i\in [n]}=\mathbf{x}$ without many competing/alternative short vectors.

Final Reduction

To improve the theoretical bound issue in point 3 above, “An Improved Low-density Subset Sum Algorithm” [CLOS’91] has proposed to use:

$$B=\left[\begin{array}{cc}\mathbf{I}& N\mathbf{a}\\ \mathbf{1}\mathbf{/}\mathbf{2}& NS\end{array}\right]={\left[\begin{array}{ccccc}1& 0& \dots & 0& N{a}_1\\ 0& 1& \dots & 0& N{a}_2\\ & & \dots & \\ 0& 0& \dots & 1& N{a}_n\\ 1/2& 1/2& \dots & 1/2& NS\end{array}\right]}_{(n+1)\times (n+1)}$$

This slightly modified reduction increase the range of SSP instances we can solve to any

$d<0.9408$. But we skip the analysis, as it’s non-essential to us, and take it as given.

To address concern 4 above, [Schnorr’93] in “Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems” on Sec. 7 build on top of [CLOS’91], added an extra column (second last column below) to control and constrain the equivalent value of

$c_{n+1}$in our previous attempt.

$$B=\left[\begin{array}{ccc}2\mathbf{I}& \mathbf{0}& N\mathbf{a}\\ \mathbf{1}& 1& NS\end{array}\right]={\left[\begin{array}{cccccc}2& 0& \dots & 0& 0& N{a}_1\\ 0& 2& \dots & 0& 0& N{a}_2\\ & & \dots & \\ 0& 0& \dots & 2& 0& N{a}_n\\ 1& 1& \dots & 1& 1& NS\end{array}\right]}_{(n+1)\times (n+2)}$$

The condition to check becomes:

$$|z_{n+1}|=1\wedge z_{n+2}=0\wedge z_1,\dots ,z_n\in \text{set}\pm 1$$

It’s not hard to verify that the foregoing condition guarantees

$(|z_i-z_{n+1}|/2{)}_{i\in [n]}=\mathbf{x}$ with overwhelming probability (since we avoid all of the 4 caveats above).

Say

$z_{n+1}=1\Rightarrow c_{n+1}=1\Rightarrow \sum c_i{a}_i=S$, and since

$(z_i:=2c_i+1{)}_{i\in [n]}\in \text{set}\pm 1\Rightarrow c_i\in \text{set}0,-1\Rightarrow |z_i-z_{n+1}|/2\in \text{set}0,1$, Wola! You can easily double-check the other case when

$z_{n+1}=-1$.

Higher-dimension SSP

Up until now, we only consider

$a_i$ as scalars. What if they are vectors of higher dimension themselves, say

$a_i=(a_{i,1},\dots ,a_{i,m}),S=(S_1,\dots ,S_m)\in {\mathbb{R}}^m$? We could flatten out all the

$m$ dimensions and use the same argument, inflating the embedding dimension but keeps the same lattice dimension for

$B^t$. Concretely:

$$B=\left[\begin{array}{ccc}2\mathbf{I}& \mathbf{0}& N\overrightarrow{a}\\ \mathbf{1}& 1& N\mathbf{S}\end{array}\right]={\left[\begin{array}{ccccccccc}2& 0& \dots & 0& 0& N{a}_{1,1}& N{a}_{1,2}& \dots & N{a}_{1,m}\\ 0& 2& \dots & 0& 0& N{a}_{2,1}& N{a}_{2,2}& \dots & N{a}_{2,m}\\ & & \dots & \\ 0& 0& \dots & 2& 0& N{a}_{n,1}& N{a}_{n,2}& \dots & N{a}_{n,m}\\ 1& 1& \dots & 1& 1& N{S}_1& N{S}_2& \dots & N{S}_m\end{array}\right]}_{(n+1)\times (n+m+1)}$$

The condition check becomes:

$$|z_{n+1}|=1\wedge z_{n+2},\dots ,z_{n+m+1}=0\wedge z_1,\dots ,z_n\in \text{set}\pm 1$$

TODO: add more analysis on the success rate or density bound?

Modular SSP

Sometimes, we are asked to solve the modular variant of SSP where values and summations are carried out in

$\mathrm{mod}q$ instead of in

$\mathbb{R}.$

TODO: add adaptation here.

One more thing

Recall the edge case of some

$a_i=a_j$ that goes outside the scope of classical definition of SSP instance, that may cause competing short vectors.

If there aren’t too many (say constant number) of these duplicates, then we can simply remove

$a_j$ and feed

$(\text{set}{a}_i\mathrm{\setminus }{a}_j,S-a_j)$ and

$(\text{set}{a}_i\mathrm{\setminus }{a}_j,S)$ to the current subset sum solver. Note the two instances corresponds to the original

$c_j=1$ and

$c_j=0$. Since our reduction in the final attempt gives a poly-time solver, we would end up a poly-time solver here too. Effectively, we are guessing

$c_j$ and trading off run-time with success probability.

This approach also works if there are logarithmic number of duplicates, as guessing all possible combination takes the power set of those duplicates, and logarithmic duplicates leads to

$O(n)$ number of tries, which still end up with poly-time solver.

However, if we go beyond log number of duplicates, then in practice, instead of suffering from super-poly runtime, we might choose to suffer from a slightly higher failure probability from the subset solver instead. Additionally, we can check more than just

$b_1^{\prime }$, but also the first few reduced basis, since there’s likelihood that the first reduced basis is the shortest competing vector while the second shortest basis corresponds to our subset solution. In terms of bound and guarantee, it’s beyond my depth for now but some statistical empirical evaluations might enlighten us.

---

1. both the screenshot and the theorem are excerpt from Regev's lecture note. ↩︎