Kannan Embedding: Solving CVP as a Shortest Vector Problem

Many measurement problems end with the same question: a device reports a point $t$ that should lie on a known lattice, but noise has pushed it off. Lattice codes in digital communication, integer ambiguity resolution in satellite positioning and rounding in signal processing all ask for the lattice point $v$ that produced $t$ . That is the closest vector problem. This guide shows the most common way to hand it to a lattice reducer: the Kannan embedding, which turns “close to the lattice” into “short in a lattice one dimension larger”. Rows of every matrix are basis vectors, as in g6k-rs.

CVP and bounded distance decoding

Given a basis $B$ of a lattice $L$ and a target $t$ , CVP asks for a lattice point nearest to $t$ . In a decoding problem we know more: $t$ was produced as

t = v + e, \qquad v \in L, \quad e \text{ small}.

When $\|e\| < \lambda_1(L)/2$ , the point $v$ is the unique closest lattice point, and the problem is called bounded distance decoding (BDD). Past that radius another lattice point can be as close as $v$ , so success means recovering the planted $v$ , not merely some nearby point. We measure noise relative to the Gaussian heuristic $\mathrm{gh}(L) \approx \sqrt{n/(2\pi e)}\,\det(L)^{1/n}$ , which estimates $\lambda_1$ for a random-looking lattice.

The embedding

The small object is the error $e$ . The relation $t - e \in L$ is affine, because of the constant $t$ , so we homogenize it: append one coordinate to every basis vector and add $t$ as a new row with an embedding factor $M$ in the new coordinate.

B' = \begin{pmatrix} B & 0 \\ t & M \end{pmatrix} \in \mathbb{Z}^{(n+1) \times (n+1)}

Every vector of the new lattice $L'$ has the form $(xB + k t,\; kM)$ for integers $x$ and $k$ . Take $k = -1$ and choose $x$ with $xB = v$ . The result is

(v - t,\; -M) = (-e,\; -M), \qquad \|(e, M)\| = \sqrt{\|e\|^2 + M^2}.

Kannan embedding at a glance

Dimension: $n + 1$ .
Determinant: $\det(L') = M \cdot \det(L)$ , because $B'$ is block triangular.
Target: $\pm(e, M)$ with norm $\sqrt{\|e\|^2 + M^2}$ .
Heuristic condition: $\sqrt{\|e\|^2+M^2} < \mathrm{gh}(L') = \sqrt{\tfrac{n+1}{2\pi e}}\,(M\det L)^{1/(n+1)}$ .
Extraction: find a reduced row whose last coordinate is $\pm M$ , flip its sign so the last entry is $+M$ , read off $e$ , and return $v = t - e$ .

The heuristic condition says the target is shorter than a typical shortest vector of a random lattice with the same volume. The planting ratio $\mathrm{gh}(L')/\|(e,M)\|$ measures the margin: larger is better. It is a heuristic for random-looking lattices, not a proof that $(e, M)$ is the shortest vector.

Choosing the embedding factor M

$M$ is a weight on one extra coordinate. Reduction minimizes the Euclidean norm, so a balanced target has every coordinate of roughly the same size. The coordinates of $e$ have typical size $\sigma$ , the per-coordinate noise level, so the balanced choice is $M \approx \sigma$ , not $M \approx \|e\| \approx \sigma\sqrt{n}$ . The difference matters. With $M = \|e\|$ the target norm grows by a factor $\sqrt 2$ , while $\mathrm{gh}(L')$ grows only like $M^{1/(n+1)}$ .

The table uses the lattice from the experiments below ( $n = 40$ , $\det(L) = 10007^{20}$ , so $\mathrm{gh}(L) \approx 153.1$ ).

$\\|e\\|/\mathrm{gh}(L)$	M	target norm	$\mathrm{gh}(L')$	planting ratio
0.5	$\sigma \approx 12.1$	77.5	147.2	1.90
0.5	$\\|e\\| \approx 76.5$	108.3	154.0	1.42
0.7	$\sigma \approx 16.9$	108.5	148.4	1.37
0.7	$\\|e\\| \approx 107.2$	151.6	155.3	1.02
0.9	$\sigma \approx 21.8$	139.5	149.3	1.07
0.9	$\\|e\\| \approx 137.8$	194.9	156.2	0.80

Both extremes fail in instructive ways:

M too large. Any vector with last coordinate $\pm M$ is $t$ minus a lattice vector. Size reduction of the new row against the reduced $B$ is exactly Babai’s nearest-plane step, and a long row is never swapped forward. The embedding degrades to Babai, and the measurements below show identical success counts.
M too small. Vectors with $k = \pm 2$ , of the form $(2t - w,\; 2M)$ for $w \in L$ , pay almost nothing for their last coordinate and can compete. $M$ must also be a positive integer if the basis stays integral, so $M = 1$ is the floor.

Measured on a fixed set of 40 random instances ( $n = 40$ , separate from the instances in the larger table below), counting how often the planted $v$ was recovered:

M	$\\|e\\|/\mathrm{gh} = 0.7$ , LLL	$\\|e\\|/\mathrm{gh} = 0.9$ , BKZ-20
1	31/40	23/40
$0.25\,\sigma$	31/40	30/40
$\sigma$	27/40	27/40
$2\sigma$	19/40	24/40
$4\sigma$	13/40	6/40
$\sqrt{n}\,\sigma \approx \\|e\\|$	13/40	6/40
$8\sqrt{n}\,\sigma$	13/40	6/40
Babai, same reduction	13/40	4/40

Anything from $M = 1$ to about $2\sigma$ works well; from $4\sigma$ upward the embedding does no better than Babai. A rule that holds up: start at $M = \lceil \sigma \rceil$ and try a smaller value if you see $\pm 2M$ in the last coordinate of short rows.

What can beat the target

The planting ratio compares the target with a random lattice. Before trusting it, check the vectors this particular construction is guaranteed to contain:

Inherited vectors $(w, 0)$ with $w \in L$ . Their length is at least $\lambda_1(L)$ , so the target must be shorter than $\lambda_1(L)$ , not only shorter than $\mathrm{gh}(L')$ .
Multiples of the target row $(kt - w,\; kM)$ with $|k| \ge 2$ . These are short when $kt$ happens to lie close to $L$ and $M$ is tiny.
Structure in L. A lattice with a dense sublattice or very short vectors (for example, one with many repeated rows) can have competitors that the Gaussian heuristic does not see. The random q-ary lattices used here have no such structure.

A complete example in Rust

The program below builds a random 30-dimensional lattice with $\det(L) = 10007^{15}$ , hides a point $v$ , adds noise with $\sigma = 17$ (so $\|e\| \approx 0.7\,\mathrm{gh}(L)$ ), and decodes it both ways after LLL and BKZ-10. It needs only g6k-rs = "=0.1.0" in Cargo.toml.

// Decode a noisy lattice point two ways: Babai nearest plane and Kannan embedding.
// Rows of every matrix are basis vectors. Cargo.toml: g6k-rs = "=0.1.0"
use g6k_rs::{BKZParams, GSO, LatticeBasis, babai_nearest_plane, bkz_reduce, lll};

const N: usize = 30; // lattice dimension
const Q: i64 = 10007; // det(L) = Q^(N/2)

// Small deterministic generator so the example needs no extra crates.
struct Rng(u64);
impl Rng {
    fn next(&mut self) -> u64 {
        self.0 = self.0.wrapping_add(0x9E3779B97F4A7C15);
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
        z ^ (z >> 31)
    }
    fn below(&mut self, m: u64) -> i64 { (self.next() % m) as i64 }
    fn gauss(&mut self) -> f64 {
        let u = ((self.next() >> 11) as f64 / (1u64 << 53) as f64).max(1e-300);
        let v = (self.next() >> 11) as f64 / (1u64 << 53) as f64;
        (-2.0 * u.ln()).sqrt() * (2.0 * std::f64::consts::PI * v).cos()
    }
}

fn reduce(b: &mut LatticeBasis) {
    let _ = lll(b);
    let _ = bkz_reduce(b, &BKZParams { block_size: 10, max_tours: 8, ..Default::default() });
}

fn main() {
    let mut rng = Rng(2);

    // 1. A known lattice: rows [Q*I | 0] and [A | I].
    let k = N / 2;
    let mut b = vec![vec![0i64; N]; N];
    for i in 0..k { b[i][i] = Q; }
    for i in k..N {
        for j in 0..k { b[i][j] = rng.below(Q as u64); }
        b[i][i] = 1;
    }

    // 2. A hidden lattice point v, received as t = v + e.
    let x: Vec<i64> = (0..N).map(|_| rng.below(21) - 10).collect();
    let v: Vec<i64> = (0..N).map(|j| (0..N).map(|i| x[i] * b[i][j]).sum()).collect();
    let sigma = 17.0; // per-coordinate noise size
    let e: Vec<i64> = (0..N).map(|_| (sigma * rng.gauss()).round() as i64).collect();
    let t: Vec<i64> = (0..N).map(|j| v[j] + e[j]).collect();
    let e_norm = e.iter().map(|&c| (c * c) as f64).sum::<f64>().sqrt();
    println!("||e|| = {:.1}", e_norm);

    // 3a. Babai nearest plane on a reduced basis.
    let mut lb = LatticeBasis::from_integers(&b);
    reduce(&mut lb);
    let gso = GSO::new(&lb);
    let tf: Vec<f64> = t.iter().map(|&c| c as f64).collect();
    let np = babai_nearest_plane(&lb, &gso, &tf);
    let babai_ok = np.closest.iter().zip(&v).all(|(a, &b)| (a - b as f64).abs() < 0.5);
    println!("Babai nearest plane: distance {:.1}, found v: {}", np.dist_sq.sqrt(), babai_ok);

    // 3b. Kannan embedding: rows [B | 0] and [t | M], with M about sigma.
    let m = sigma.round() as i64;
    let mut rows: Vec<Vec<i64>> = b.iter().map(|r| { let mut r = r.clone(); r.push(0); r }).collect();
    let mut last = t.clone();
    last.push(m);
    rows.push(last);
    let mut kb = LatticeBasis::from_integers(&rows);
    reduce(&mut kb);

    // 4. Extract: a row with last coordinate +-M is +-(e, M).
    for (i, r) in kb.basis.iter().enumerate() {
        if (r[N].abs() - m as f64).abs() < 0.5 {
            let s = r[N].signum();
            let e_hat: Vec<i64> = (0..N).map(|j| (s * r[j]).round() as i64).collect();
            let v_hat: Vec<i64> = (0..N).map(|j| t[j] - e_hat[j]).collect();
            println!("Kannan: row {} has last coordinate {}, norm {:.1}, found v: {}",
                i, r[N], kb.norm_sq(i).sqrt(), v_hat == v);
            break;
        }
    }
}

Output with seed 2 (cargo run --release):

||e|| = 100.4
Babai nearest plane: distance 171.7, found v: false
Kannan: row 0 has last coordinate 17, norm 101.8, found v: true

This seed was chosen to show a case where the two methods disagree; with most seeds at this noise level both succeed. Babai returned a lattice point at distance 171.7, farther than the true error of 100.4, because $e$ did not fit inside the Gram–Schmidt box of the reduced basis. The embedding found $(e, 17)$ as the first reduced row, with norm $\sqrt{100.4^2 + 17^2} \approx 101.8$ .

Measured success rates at n = 20, 30, 40

Each cell counts recoveries of the planted point over 40 random instances (fixed seeds, identical instances in every column). Kannan uses $M$ equal to $\sigma$ rounded to the nearest integer. Babai runs nearest plane on the basis reduced the same way.

n	$\\|e\\|/\mathrm{gh}$	LLL: Babai / Kannan	BKZ-10: Babai / Kannan	BKZ-20: Babai / Kannan
20	0.5	40 / 40	39 / 40	40 / 40
20	0.7	36 / 40	33 / 40	36 / 40
20	0.9	21 / 30	25 / 31	19 / 30
20	1.1	8 / 15	9 / 18	7 / 17
30	0.5	38 / 40	38 / 40	39 / 40
30	0.7	25 / 37	33 / 40	25 / 40
30	0.9	14 / 19	14 / 34	10 / 36
30	1.1	2 / 3	3 / 12	4 / 10
40	0.5	36 / 40	39 / 40	40 / 40
40	0.7	16 / 25	25 / 40	14 / 39
40	0.9	4 / 7	4 / 19	3 / 30
40	1.1	0 / 2	0 / 6	0 / 8

Three patterns stand out.

Up to half the Gaussian heuristic, Babai is enough. Both methods recover nearly every point. Babai is also cheaper when you decode many targets: reduce the basis once, then each target costs one nearest-plane pass. The embedding needs a fresh reduction per target.
Between 0.7 and 0.9, the embedding pulls ahead, and stronger reduction widens the gap. At $n = 40$ and $\|e\|/\mathrm{gh} = 0.9$ , BKZ-20 on the embedding decodes 30 of 40 points against Babai’s 3.
Past the Gaussian heuristic, nothing is reliable. At 1.1 the error is larger than half the expected shortest vector, so the planted point need not be the closest lattice point, and no decoder can be expected to return it.

With 40 trials a count moves by a few points from sampling alone, which explains small inversions such as Babai doing slightly better after BKZ-10 than after BKZ-20 in some rows. On the $n = 40$ lattice the reductions themselves are ordered as expected: the first basis vector has norm 220.6 after LLL, 178.4 after BKZ-10, 174.3 after BKZ-20 and 161.8 after BKZ-30.

Scaling up

The embedding adds a single dimension, so the cost is that of reducing an $(n+1)$ -dimensional lattice well enough to expose a vector that is shorter than expected by the planting ratio. Smaller ratios need larger BKZ block sizes, which is where sieve-backed BKZ and progressive strategies from the recipes page come in; the BKZ chapter explains the trade-off. The same homogenization step reappears whenever an equation has a constant term, most directly in short solutions of Ax = b.

Common mistakes

Setting M to the full error norm. The target becomes $\sqrt 2$ times longer and the embedding behaves like Babai. Match $M$ to one coordinate of $e$ .
Reading the wrong row. The first reduced row is not always the target. Search for a row whose last coordinate is $\pm M$ and verify $t - e \in L$ .
Forgetting the sign. Reduction returns $(e, M)$ or $(-e, -M)$ . Normalize so the last coordinate is $+M$ before subtracting.
Mixing conventions. With column bases the new vector is a column and $t$ goes in the last column. Pick rows or columns and keep it throughout.
Unscaled coordinates. If some coordinates of $e$ are much larger than others, weight them first so the error is roughly isotropic, as in Diophantine approximation.

7.4 Closest vectors by Kannan embedding