Knapsack Cryptosystem — subset-sum ciphertexts broken by low-density lattice reduction

Knapsack (subset-sum) encryption sends a secret bit vector x_i ∈ {0,1} as a single integer s = Σ a_i x_i over public weights a_i; recovering x is subset-sum, NP-hard in general but *easy at low density* via the Lagarias–Odlyzko lattice attack.

The signal that betrays it

- The ciphertext (or a per-message quantity you're asked to invert) is one integer that is a sum of a chosen subset of public values — "which subset of these N numbers adds up to the target" is the whole challenge, however it's dressed up. - A public list of weights a_i accompanies the sum s, and the secret is *which* weights were used (or, in the trapdoor variant Merkle-Hellman, the same shape but with a hidden superincreasing structure disguised by a modular multiplier). - Compute the density d = n / log2(max a_i) where n is the number of weights. If d is comfortably below the ~0.9408 threshold (Coster–Joux–LaMacchia–Odlyzko–Schnorr–Stern's improvement on Lagarias–Odlyzko's original 0.6463 bound), the lattice attack is expected to succeed — this is the number-you-compute-first signal, not a vague impression. Textbook Merkle-Hellman keys land far below this threshold by construction, which is exactly why they don't survive. - If the weights themselves look superincreasing after undoing an obvious modular scaling, you're looking at the *trapdoor* case, not the general low-density case — see below, it's a different (easier) path.

How to exploit it

Path A — trapdoor leaks (Merkle-Hellman style). If the private superincreasing sequence and the modular multiplier/modulus are recoverable or given, skip lattice work entirely: invert the multiplier mod the modulus, apply it to the ciphertext, then solve the now-superincreasing subset sum by the standard greedy algorithm (take the largest remaining element ≤ the remaining target, subtract, repeat). This is the intended decryption path, not an attack, but shows up in challenges as "reconstruct the private key from these parameters."

Path B — general low-density lattice attack (Lagarias–Odlyzko / CJLOSS). This is the one to reach for whenever no trapdoor is given, or the "trapdoor" is exactly what you're trying to break:

1. Confirm density d = n / log2(max a_i) is low (see signal above). This is the single most useful sanity check before investing in lattice construction — if density is high (close to or above 1), the attack is not expected to work and you should look elsewhere. 2. Build the LO/CJLOSS lattice: an n×n identity block for the unknown bits x_i, augmented with a column of the scaled weights N·a_i (N a large weighting constant, roughly ⌈√n⌉ or 2^(n/2), chosen to force the short vector to have 0/1 entries in the identity part and near-zero in the weighted column), then append one more row (0,...,0, N·s) encoding the target sum. 3. Run LLL Reduction — the polynomial-time workhorse behind almost every lattice attack on this basis (LLL, not full BKZ — LLL is usually sufficient at this density and is dramatically faster; escalate to BKZ only if LLL returns nothing usable). 4. Scan the reduced basis for a vector whose first n coordinates are all 0/1 (or, in the ±1 centered variant, all in {-1,+1} which you then remap to {0,1}). That vector's leading block *is* x. 5. Always verify: recompute Σ a_i x_i from the candidate and confirm it equals s before trusting it. LLL can return multiple short vectors or none that look right on the first pass — verification is cheap and catches false positives immediately.

``python from sage.all import Matrix, ZZ, identity_matrix n = len(a) N = ZZ(1) << (n // 2) # weighting constant forcing 0/1 shortness B = identity_matrix(ZZ, n).augment(Matrix(ZZ, n, 1, [N * ai for ai in a])) B = B.stack(Matrix(ZZ, 1, n + 1, [0] * n + [N * s])) for v in B.LLL(): if set(v[:n]) <= {0, 1}: print(v[:n]) ``

This construction and the density thresholds rest on Lattice Fundamentals — encoding a bounded unknown as a short vector (encoding a bounded unknown as a short lattice vector) and LLL Reduction — the polynomial-time workhorse behind almost every lattice attack (the reduction step that actually finds it). If the trapdoor route (Path A) applies, it's ordinary Euler's Totient — the RSA key-math backbone, and why it's not the exponent you want to leak-flavored modular inverse work, not lattice work at all.

What does NOT work

- Brute-forcing the subset directly is off the table for any realistic n (even n≈50 is 2^50 subsets) — don't reach for meet-in-the-middle unless n is small enough (roughly n ≤ 40-ish, and even then it costs real memory) or the density is *high*, where the lattice attack's guarantees weaken and combinatorial methods become relatively more competitive. - Assuming the lattice attack always succeeds — it's a heuristic, not a proof, outside the density bound. Near the 0.9408 threshold or above it, LLL frequently returns short vectors that are *not* the 0/1 target vector, or fails to find one at all. Don't skip step 5 (verification) and don't burn time re-running LLL with cosmetic parameter tweaks hoping for a different answer if the density itself is the problem — increasing N or shuffling weight ordering rarely rescues a high-density instance. - Treating every "sum of a subset" challenge as this attack without checking density first. If the challenge author deliberately kept n small and weights dense (density near or above 1), this is a genuinely hard subset-sum instance and the intended path is elsewhere (e.g. a structural leak, a padding/side-channel oracle, or a much smaller search space than it first appears) — the lattice attack is not a universal subset-sum solver. - Reusing the trapdoor-decryption greedy algorithm on non-superincreasing weights. The greedy "take largest ≤ remaining target" method only works because a superincreasing sequence guarantees uniqueness at each step; run it on the disguised public weights (or any non-superincreasing set) and it silently produces a wrong answer that happens to look plausible — always verify against s, per step 5 above, before trusting *any* recovered subset.

Field-tested note

the density computation is worth doing before writing a single line of lattice code — it's a one-line sanity check (n / log2(max(a))) that tells you in seconds whether you're about to spend an hour building a lattice for an instance that was never going to fall to it.