Korkine–Zolotarev lattice basis reduction algorithm

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

Although the KZ reduction has exponential complexity versus the polynomial complexity of the LLL reduction algorithm, it is preferred for solving sequences of Closest Vector Problems (CVPs) in a lattice, where it may be more efficient.

History

The definition of a KZ-reduced basis was given by A. Korkine and G. Zolotareff in 1877, a strengthened version of Hermite reduction. The first algorithm for constructing a KZ-reduced basis was given in 1983 by Kannan.

Definition

A KZ-reduced basis for a lattice is defined as follows:

Given a basis

$\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\},$

define its Gram–Schmidt process orthogonal basis

$\mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{n}^{*}\},$

and the Gram-Schmidt coefficients

$\mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}$, for any $1\leq j<i\leq n$.

Also define projection functions

$\pi _{i}(\mathbf {x} )=\sum _{j\geq i}{\frac {\langle \mathbf {x} ,\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}\mathbf {b} _{j}^{*}$

which project $\mathbf {x}$ orthogonally onto the span of $b_{i}^{*},\cdots ,b_{n}^{*}$.

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

1. $\mathbf {b} _{i}^{*}$ is the shortest nonzero vector in $\pi _{i}({\mathcal {L}}(\mathbf {B} ))$

1. For all $j<i$, $\left|\mu _{i,j}\right|\leq 1/2$

Note that the second condition guarantees that the reduced basis is length-reduced (adding an integer multiple of one basis vector to another will not decrease its length); the same condition is used in the LLL reduction.

Algorithm

Given a lattice with full column rank matrix $\mathbf {A} \in \mathbb {R} ^{m\times n}$, a KZ-reduced basis can be constructed as follows:

References

• Korkine, A.; Zolotareff, G. (1877). "Sur les formes quadratiques positives". {{cite journal}}: Cite journal requires |journal= (help)

• Lyu, Shanxiang; Ling, Cong (2017). "Boosted KZ and LLL Algorithms" (PDF). {{cite journal}}: Cite journal requires |journal= (help)

• Wen, Jinming; Chang, Xiao-Wen (2018). "On the KZ Reduction" (PDF). {{cite journal}}: Cite journal requires |journal= (help)

• Micciancio, Daniele; Goldwasser, Shafi (2002). Complexity of Lattice Problems. pp. 131–136.

• Zhang, Wen; Qiao, Sanzheng; Wei, Yimin (2012). "HKZ and Minkowski Reduction Algorithms for Lattice-Reduction-Aided MIMO Detection" (PDF). {{cite journal}}: Cite journal requires |journal= (help)