7.1 Lattice embedding basics

What is a lattice embedding?

Lattice reduction algorithms take a basis and return a better one whose first vectors are short. They know nothing about the problem you care about. An embedding is the bridge: a lattice, written as a basis, in which the answer to your problem appears as a short vector (or as the vector closest to a target). If the embedding is good, the reducer hands you the answer. If it is not, the reducer returns some other short vector and you learn nothing.

Throughout these guides we use the row convention: the rows of a matrix $B$ are the basis vectors, and the lattice is $L(B)=\{xB : x\in\mathbb{Z}^n\}$. This matches g6k-rs, fplll and most of the cryptographic literature. If you copy a formula from a source that uses columns, transpose it first.

The numbers that decide success

Four quantities tell you whether a construction has a chance. The dimension $n$ (the rank) and the determinant $\det(L)=\sqrt{\det(BB^\top)}$ do not depend on which basis you write down. The first minimum $\lambda_1(L)$ is the length of the shortest nonzero vector; you want your target to be it. The Gaussian heuristic predicts how long the shortest vector of a random lattice with the same dimension and determinant would be:

If your target has norm $t$, the ratio $\mathrm{gh}(L)/t$ is its planting ratio. A ratio well above 1 says the target is unusually short compared with what the rest of the lattice should offer. That is a heuristic signal, not a guarantee. Structured lattices can contain accidental short vectors, and in very low dimensions the heuristic is rough, as the example below shows.

Warm-up: a relation you can check by hand

Take $a=(5,8,13)$ and look for a short integer vector $x$ with $a\cdot x=0$. A few seconds of staring gives $x=(1,1,-1)$, since $5+8-13=0$, with norm $\sqrt{3}$. An exhaustive search over small vectors confirms that nothing shorter solves the equation. With three numbers you can do this by eye. With numbers in the thousands, or with dozens of unknowns, you cannot, and that is where the embedding earns its keep.

Worked example: short solutions of a·x = 0

Now take $a=(271,828,1828)$. The small object is $x$. The constraint is one exact linear equation. To place $x$ in a lattice, give each unknown its own row and append a column that computes the equation, multiplied by a scaling factor $N$:

Any integer combination $xB$ carries $x$ in its first three coordinates and $N(a\cdot x)$ in the last. If $a\cdot x\neq 0$ then that last coordinate is at least $N$ in absolute value, because $a\cdot x$ is a nonzero integer. So once $N$ is larger than the norm of the shortest true solution, every vector that breaks the equation is longer than one that satisfies it. The equation becomes a coordinate that is forced to zero.

// Short integer solutions of a·x = 0 via the kernel embedding [I | N·a].
use g6k_rs::{lll, LatticeBasis, GSO};

fn kernel_embedding(a: &[i64], n_scale: i64) -> LatticeBasis {
    let n = a.len();
    let rows: Vec<Vec<i64>> = (0..n)
        .map(|i| {
            let mut row = vec![0; n + 1];
            row[i] = 1; // identity block records the coefficients x
            row[n] = n_scale * a[i]; // last coordinate = N · (a·x)
            row
        })
        .collect();
    LatticeBasis::from_integers(&rows)
}

fn main() {
    let a = [271i64, 828, 1828];
    for n_scale in [1, 5, 10, 20, 31] {
        let mut basis = kernel_embedding(&a, n_scale);
        let _ = lll(&mut basis);
        let b0: Vec<i64> = basis.basis[0].iter().map(|&v| v.round() as i64).collect();
        let x = &b0[..a.len()];
        let ax: i64 = x.iter().zip(&a).map(|(xi, ai)| xi * ai).sum();
        println!(
            "N = {:>2}: b0 = {:?}, |b0| = {:.3}, a·x = {}{}",
            n_scale,
            b0,
            basis.norm_sq(0).sqrt(),
            ax,
            if ax == 0 { "  <- solution" } else { "" }
        );
    }

    // Audit: the solutions form a rank-2 lattice (rows whose last coordinate is 0).
    let mut basis = kernel_embedding(&a, 1000);
    let _ = lll(&mut basis);
    let kernel_rows: Vec<Vec<i64>> = basis
        .basis
        .iter()
        .filter(|r| r[a.len()] == 0.0)
        .map(|r| r[..a.len()].iter().map(|&v| v.round() as i64).collect())
        .collect();
    let kernel = LatticeBasis::from_integers(&kernel_rows);
    let gso = GSO::new(&kernel);
    println!("kernel rank = {}, det = {:.3}", kernel.rows, (gso.log_det() / 2.0).exp());
    println!("gh = {:.3}, shortest found = {:.3}", gso.gaussian_heuristic(), kernel.norm_sq(0).sqrt());
}

Running it with cargo run --release against g6k-rs 0.1.0 prints:

N =  1: b0 = [-8, -4, 3, 4], |b0| = 10.247, a·x = 4
N =  5: b0 = [6, -13, 5, 10], |b0| = 18.166, a·x = 2
N = 10: b0 = [6, -13, 5, 20], |b0| = 25.100, a·x = 2
N = 20: b0 = [20, -22, 7, 0], |b0| = 30.545, a·x = 0  <- solution
N = 31: b0 = [20, -22, 7, 0], |b0| = 30.545, a·x = 0  <- solution
kernel rank = 2, det = 2024.996
gh = 15.399, shortest found = 30.545

With $N\le 10$ the first reduced vector is short but useless: its last coordinate is $N(a\cdot x)\neq 0$, so it is not a solution. The reducer found a vector that trades a small violation of the equation for small coefficients, which is exactly what the Euclidean norm rewards. From $N=20$ on, the first vector is $(20,-22,7)$. Check it by hand: $271\cdot 20-828\cdot 22+1828\cdot 7=5420-18216+12796=0$.

The safe rule is $N>t$, where $t$ is the norm of the solution you expect, here $\sqrt{933}\approx 30.5$. The run shows that 20 already suffices in practice: the rule is sufficient, not necessary. Pick the smallest $N$ that clearly dominates. A much larger one still works but inflates the entries, which costs precision and time in bigger problems.

The audit lines are worth reading. The solutions form a rank-2 lattice with determinant $\|a\|\approx 2025.0$ (this holds because $\gcd(271,828,1828)=1$). The Gaussian heuristic predicts a shortest vector of about 15.4, but the true minimum is 30.5. In dimension 2 and for a lattice defined by one equation, the heuristic is simply rough. That is why step 5 of the recipe always ends with checking the answer, not with trusting the estimate.

Adding a constant: homogenization

Suppose instead you need a short $x$ with $a\cdot x=c$ for $c=3641$. The solutions of an equation with a constant term are not a lattice: they are a shifted copy of one, and the zero vector is not among them. The fix is to introduce a new unknown $t$ and solve $a\cdot x-c\,t=0$. That is homogeneous again, so it has a lattice of solutions, and any solution with $t=\pm 1$ gives an answer to the original equation. One extra row carries the constant, and its homogenizing coordinate gets a weight $M$:

This is the same trick as the Kannan embedding for closest-vector problems, and it reappears in every later guide. Here is the construction and the result for $M=1$ and $M=40$, with $N=100$:

// Excerpt: solve a·x = c for a short x by homogenizing.
// Rows [I | 0 | N·a] and one extra row [0 | M | -N·c].
fn affine_embedding(a: &[i64], c: i64, n_scale: i64, m: i64) -> LatticeBasis {
    let n = a.len();
    let mut rows = Vec::new();
    for i in 0..n {
        let mut row = vec![0; n + 2];
        row[i] = 1;
        row[n + 1] = n_scale * a[i];
        rows.push(row);
    }
    let mut last = vec![0; n + 2];
    last[n] = m; // homogenizing coordinate: the target has t = ±1 here
    last[n + 1] = -n_scale * c;
    rows.push(last);
    LatticeBasis::from_integers(&rows)
}

// In main: a = [271, 828, 1828], c = 3641, N = 100, then M = 1 and M = 40.
// After lll(&mut basis), look for a row with last coordinate 0 and
// homogenizing coordinate ±M, flip its sign if needed, and check a·x = c.

M = 1
  b0 = [3, -1, 2, 1, 0]  |b0| = 3.873
  b1 = [2, -16, -5, -6, 0]  |b1| = 17.916
  b2 = [-39, -14, 42, 15, 0]  |b2| = 60.877
  b3 = [17, 10, -19, -6, 100]  |b3| = 103.856
  x = [3, -1, 2], a·x = 3641 (want 3641)
  rank 3, det 4166.2, gh 6.744, target 3.873, gh/t 1.74
M = 40
  b0 = [20, -22, 7, 0, 0]  |b0| = 30.545
  b1 = [3, -1, 2, 40, 0]  |b1| = 40.175
  b2 = [-44, -43, 26, 0, 0]  |b2| = 66.791
  b3 = [15, 26, -14, 0, 100]  |b3| = 105.342
  x = [3, -1, 2], a·x = 3641 (want 3641)
  rank 3, det 81081.6, gh 18.140, target 40.175, gh/t 0.45

With $M=1$ the first vector is $(3,-1,2,1,0)$: the coefficients $x=(3,-1,2)$, the homogenizing coordinate $t=1$, and an exact equation. Check: $271\cdot 3-828+1828\cdot 2=3641$. The target norm is $\sqrt{15}\approx 3.87$ and the planting ratio is 1.74, so the target stands out.

With $M=40$ the homogenizing coordinate dominates the target's length, now 40.2. The kernel vector $(20,-22,7,0,0)$, which has $t=0$ and solves only the homogeneous equation, is shorter and takes first place. The planting ratio drops to 0.45. In this tiny example the answer still appears as the second row, but in a larger lattice it would be buried. Choose $M$ on the order of the typical size of one coordinate of $x$, then compare against competitors like these.

The design levers

Extracting and checking the answer

An embedding is only finished when you can read the answer off a reduced basis and verify it independently. The pattern is always the same:

• Filter rows by structure. Keep rows whose enforced coordinates are zero and whose homogenizing coordinate is $\pm M$. Do not assume the answer is row 0.
• Normalize the sign. If $v$ is in the lattice, so is $-v$. Flip the row so the homogenizing coordinate is $+M$.
• Undo the scaling. Divide weighted coordinates by their weights and round.
• Verify in exact integer arithmetic. Recompute $a\cdot x$ with integers. The reducer works in floating point, so its output must be checked, not trusted.

Common mistakes

• Mixing row and column conventions. A formula written for columns, used as rows, describes a different lattice and fails silently.
• An unbalanced target. If one coordinate of the answer is 1000 times the others, the reducer prefers some other vector. Weight the coordinates.
• N too small or too large. Too small, and the reducer returns near-solutions; too large, and entries grow for no benefit.
• Treating the Gaussian heuristic as a proof. It predicts random lattices. Structured ones, and low-dimensional ones, can differ by a factor of two or more, as the kernel example shows.
• Putting an inequality in the basis. A lattice cannot express “$|x_i|\le 5$”. Express a bound as shortness, and enforce it with weights.

Next, 7.2 Integer relations applies the same scaling idea to real numbers: recovering a polynomial with integer coefficients from the decimal digits of one of its roots. The g6k-rs recipes page shows how to set up the crate used here.

Further reading

Daniele Micciancio and Shafi Goldwasser's Complexity of Lattice Problems (Springer, 2002) covers the Kannan embedding and its analysis. Phong Nguyen and Brigitte Vallée (eds.), The LLL Algorithm: Survey and Applications (Springer, 2010), collects many embeddings in its application chapters. The code on this page uses g6k-rs 0.1.0 from crates.io.