Hidden Subset Sum - Knapsack Recovery via Lattice Reduction (LLL)

Updated 19 Sep 2026

• •

  What it is

  • •

    If a secret is encoded as a linear combination $T = \sum_i x_i \cdot a_i$ of known large coefficients $a_i$ with small, unknown integer values $x_i$ (e.g. character codes, weighted by very large per-position constants), the $x_i$ can often be recovered directly from $T$ and the $a_i$ alone — without any brute-force search — by constructing a lattice whose basis encodes this relationship and running LLL to find its shortest vector. The vector $(x_1, \dots, x_n, 0)$ is a genuine lattice member (it equals $\sum_i x_i \cdot \text{row}_i - 1\cdot\text{row}_{\text{target}}$) and, because the $x_i$ are small while the $a_i$ are huge, it's dramatically shorter than almost any other lattice vector — so LLL, designed to find short vectors, locates it directly.

• •

  When to apply

  • •

    A "hidden message" or secret is scaled and summed into one large number using known, very large per-position weights (the classic hidden-subset-sum / low-density-knapsack setup) — a strong tell is any construction obfuscating small values (character codes, bits) by multiplying each by a large, distinct, publicly-computable coefficient and summing into a single huge integer.

• •

  Math

  • •

    For the LLL basis $B = \begin{pmatrix}I_n & \vec a \\ \vec 0 & -T\end{pmatrix}$ (row $i<n$: standard basis vector $e_i$ concatenated with $a_i$; final row: zero vector concatenated with $-T$), the target vector $(x_1,\dots,x_n,0)$ is a lattice point since it equals $\sum x_i \cdot \text{row}_i + 1 \cdot \text{row}_{\text{last}}$. Success depends on the $a_i$ having enough bits of entropy relative to the bound on the $x_i$ — too little separation and LLL finds other accidentally-short combinations instead of the true hidden vector.

• •

  Worked example

  • •

    With a hidden-vector lattice, LLL may return several comparably short rows. For each structured row, undo the scaling, check every recovered coefficient is inside its promised bound, recompute the subset sum exactly, and retain all passing candidates. A shortest-looking row is not a correctness test.

• •

  SageMath

  • •

    M = Matrix(ZZ, N+1, N+1)
    for i in range(N):
            M[i, i] = 1
            M[i, N] = a[i]
    M[N, N] = -T
    reduced = M.LLL()
    for row in reduced:
            if row[N] == 0 and any(row[:N]):
                x_recovered = row[:N]   # up to an overall sign
                break
    

• •

  Cards

  • •

    What makes the true hidden vector so much shorter than other lattice vectors, letting LLL find it?

    • •

      The unknowns (x_i) are small while the coefficients (a_i) are huge — the target vector's norm is dominated by the small x_i values, while essentially any other integer combination produces something enormously larger.

  • •

    What happens if the known coefficients don't have enough bits of entropy relative to the bound on the unknowns?

    • •

      LLL may find multiple short vectors that aren't the true hidden values, since the intended vector isn't dramatically shorter than accidental combinations — the attack becomes unreliable.

◌ Explore connections in Graph view