Lattice Fundamentals — encoding a bounded unknown as a short vector

A lattice is the set of all integer linear combinations of basis vectors b_1..b_n in R^m: L = { sum c_i b_i : c_i in Z }; the same lattice has infinitely many bases, related by unimodular (determinant ±1) transforms, and every lattice attack in this wiki reduces to one of two hard problems on it — SVP (find the shortest non-zero vector) and CVP (find the lattice point closest to an arbitrary target). A "good" basis — short, near-orthogonal vectors — solves both approximately and fast; a "bad" basis (long, skewed vectors) makes even a computer struggle, which is exactly why basis reduction is the whole game.

The signal that gives it away

A challenge is lattice-shaped when it hides one or more small unknowns tied together by a linear (or modular-linear) relation, and brute-forcing the unknown directly is too big but its *smallness relative to the modulus/other quantities* is itself exploitable. Concretely, watch for:

- Short/low-weight keystreams or error terms. - Small RSA/DSA/ECDSA nonce or key bits (a few leaked or biased bits per sample). - Subset-sum / low-density knapsack ciphertexts. - Any relation of the shape "find integers x_i, all small, with sum a_i x_i = 0 (mod N)" — the modular residue is known, the small integers are not.

The rule of thumb carried over from field use: boundedness is the tell. If the challenge would be unsolvable by brute force *unless* you already knew the secret was small, that boundedness is precisely what a lattice construction turns into "shortest vector in a lattice I can build" — coppersmith-style small modular roots (Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction), partial-nonce leaks (Hidden Number Problem — recovering a secret from many small-bounded-error samples, DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery), low-density subset sums (Knapsack Cryptosystem — subset-sum ciphertexts broken by low-density lattice reduction), and schemes where a short vector is the secret *by design* (NTRU Fundamentals — recovering the short (f,g) key pair via lattice reduction, LWE Fundamentals — recognizing and breaking noisy linear equations mod q) all fire this same recognition pattern.

How to exploit it

1. Express the relation as rows of an integer matrix. Each unknown becomes a coordinate; each known relation — including "this quantity is only known mod N" — becomes a row. 2. **Scale/weight the columns so the actual planted solution is the *shortest* vector in the lattice, not merely *a* short one. This weighting step is the real craft; get it wrong and reduction will faithfully return the true shortest vector of the lattice you built — it just won't be the one you wanted. Balance magnitudes with diagonal weights so the bound you know (on the nonce, the error, the subset-sum coefficients) dominates the geometry. 3. Reduce the basis** (see LLL Reduction — the polynomial-time workhorse behind almost every lattice attack) into a short, near-orthogonal one in polynomial time, then inspect the short rows for the planted small values. 4. For "closest vector" framings — where the target isn't itself a lattice point — use embedding (append the target as an extra row and re-reduce) or apply Babai's nearest-plane rounding on the already-reduced basis. 5. Modular constraints become extra rows carrying the modulus `N` on the diagonal, so the lattice only "knows" each relation up to that modulus rather than as an exact integer equation.

Minimal shape (Sage): ``python from sage.all import Matrix, ZZ M = Matrix(ZZ, [[1, 0, a0], [0, 1, a1], [0, 0, N]]) short = M.LLL()[0] # candidate small solution ``

What does NOT work

- Feeding LLL an unweighted/unscaled matrix and expecting the planted vector to pop out. If the column scales aren't balanced so the true solution is genuinely shortest, LLL still returns *a* correct shortest vector for the lattice you built — it's just not the one that decodes your secret. When a candidate row "looks short but wrong," the weighting is almost always the bug, not the reduction step. - Reaching for an exact SVP/CVP solver. Exact SVP (Euclidean norm) is only known NP-hard under randomized reductions — a deterministic polynomial-time reduction remains an open problem, and no efficient exact algorithm is known regardless; the polynomial-time part only comes from LLL's *approximate* guarantee (the found vector is within a factor 2^((n-1)/2) of the true shortest, per the standard analysis — in practice, often exact or very close). If a correctly-built lattice needs exact solving to work, the construction — not the algorithm — is the actual problem. - Forcing an exactly-known relation through a lattice. If the tie between unknowns is a fully known linear formula (not merely "close to" one), that's a direct linear-algebra solve, not a lattice problem — see Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula instead; a lattice embedding wastes effort a small linear system would settle instantly. - Trusting the first short row without verification. A vector with the right bit-length and range can still be numerically shortest yet semantically wrong — always re-derive and check the recovered values against the original relation before spending more time downstream.

Related

LLL Reduction — the polynomial-time workhorse behind almost every lattice attack Hidden Number Problem — recovering a secret from many small-bounded-error samples Knapsack Cryptosystem — subset-sum ciphertexts broken by low-density lattice reduction Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery NTRU Fundamentals — recovering the short (f,g) key pair via lattice reduction LWE Fundamentals — recognizing and breaking noisy linear equations mod q