Korkine–Zolotarev lattice basis reduction algorithm

Template:Distinguish

The Korkine–Zolotarev (KZ) lattice basis reduction algorithm or Hermite–Korkine–Zolotarev (HKZ) algorithm is a lattice reduction algorithm.

For lattices in $ℝ^{n}$ it yields a lattice basis with orthogonality defect at most $n^{n}$ , unlike the $2^{n^{2} / 2}$ bound of the LLL reduction.^[1] KZ has exponential complexity versus the polynomial complexity of the LLL reduction algorithm, however it may still be preferred for solving multiple closest vector problems (CVPs) in the same lattice, where it can be more efficient.

History

The definition of a HKZ-reduced basis was first given by Hermite in his second letter to Jacobi in 1845 and later also by Aleksandr Korkin and Yegor Ivanovich Zolotarev in 1877. The first algorithm for constructing a HKZ-reduced basis was given in 1983 by Kannan.^[2] and later improved by Claus Schnorr, who also introduced a practical variant known as block Korkine-Zolotarev (BKZ) algorithm in 1987.^[3]

Definition

A KZ-reduced basis for a lattice is defined as follows:^[4]

Given a basis

𝐁 = {𝐛_{1}, 𝐛_{2}, \dots, 𝐛_{n}},

define its Gram–Schmidt process orthogonal basis

𝐁^{*} = {𝐛_{1}^{*}, 𝐛_{2}^{*}, \dots, 𝐛_{n}^{*}},

and the Gram-Schmidt coefficients

μ_{i, j} = \frac{⟨ 𝐛_{i}, 𝐛_{j}^{*} ⟩}{⟨ 𝐛_{j}^{*}, 𝐛_{j}^{*} ⟩}

, for any

1 \leq j < i \leq n

.

Also define projection functions

π_{i} (𝐱) = \sum_{j \geq i} \frac{⟨ 𝐱, 𝐛_{j}^{*} ⟩}{⟨ 𝐛_{j}^{*}, 𝐛_{j}^{*} ⟩} 𝐛_{j}^{*}

which project $𝐱$ orthogonally onto the span of $𝐛_{i}^{*}, \dots, 𝐛_{n}^{*}$ .

Then the basis $B$ is KZ-reduced if the following holds:

$𝐛_{i}^{*}$ is the shortest nonzero vector in $π_{i} (ℒ (𝐁))$
For all $j < i$ , $| μ_{i, j} | \leq 1 / 2$

Note that the first condition can be reformulated recursively as stating that $𝐛_{1}$ is a shortest vector in the lattice, and ${π_{2} (𝐛_{2}), \dots π_{2} (𝐛_{n})}$ is a KZ-reduced basis for the lattice $π_{2} (ℒ (𝐁))$ .