Korkine–Zolotarev lattice basis reduction algorithm
The Korkine–Zolotarev 'lattice basis reduction algorithm or Hermite–Korkine–Zolotarev algorithm' is a lattice reduction algorithm.
For lattices in it yields a lattice basis with orthogonality defect at most, unlike the bound of the LLL reduction. 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 in the same lattice, where it can be more efficient.
History
The definition of a KZ-reduced basis was given by Aleksandr Korkin and Yegor Ivanovich Zolotarev in 1877, a strengthened version of Hermite reduction. The first algorithm for constructing a KZ-reduced basis was given in 1983 by Kannan.The block Korkine-Zolotarev algorithm was introduced in 1987.
Definition
A KZ-reduced basis for a lattice is defined as follows:Given a basis
define its Gram–Schmidt process orthogonal basis
and the Gram-Schmidt coefficients
Also define projection functions
which project orthogonally onto the span of.
Then the basis is KZ-reduced if the following holds:
Note that the first condition can be reformulated recursively as stating that is a shortest vector in the lattice, and is a KZ-reduced basis for the lattice.
Also note that the second condition guarantees that the reduced basis is length-reduced ; the same condition is used in the LLL reduction.