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.

For lattices in ${\displaystyle \mathbb {R} ^{n}}$It yields a lattice basis with orthogonality defect at most ${\displaystyle n^{n}}$, unlike the ${\displaystyle 2^{n/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 sequences of Closest Vector Problems (CVPs) in a lattice, where it can 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.^[2]

The Block Korkine-Zolotarev (BKZ) algorithm was introduced in 1987.^[3]

Definition[]

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

Given a basis

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

define its Gram–Schmidt process orthogonal basis

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

and the Gram-Schmidt coefficients

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

Also define projection functions

${\displaystyle \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 ${\displaystyle \mathbf {x} }$ orthogonally onto the span of ${\displaystyle \mathbf {b} _{i}^{*},\cdots ,\mathbf {b} _{n}^{*}}$.

Then the basis ${\displaystyle B}$ is KZ-reduced if the following holds:

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

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

Note that the first condition can be reformulated recursively as stating that ${\displaystyle \mathbf {b} _{1}}$ is a shortest vector in the lattice, and ${\displaystyle \{\pi _{1}(\mathbf {b} _{2}),\cdots \pi _{1}(\mathbf {b} _{n})\}}$ is a KZ-reduced basis for the lattice ${\displaystyle \pi _{1}({\mathcal {L}}(\mathbf {B} ))}$.

Also 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.

Notes[]

References[]

• Korkine, A.; Zolotareff, G. (1877). "Sur les formes quadratiques positives". Mathematische Annalen. 11 (2): 242–292. doi:10.1007/BF01442667. S2CID 121803621.

• Lyu, Shanxiang; Ling, Cong (2017). "Boosted KZ and LLL Algorithms" (PDF). IEEE Transactions on Signal Processing. 65 (18): 4784–4796. arXiv:1703.03303. doi:10.1109/TSP.2017.2708020. S2CID 16832357.

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

• Micciancio, Daniele; Goldwasser, Shafi (2002). Complexity of Lattice Problems. pp. 131–136. doi:10.1007/978-1-4615-0897-7. ISBN 978-1-4613-5293-8.

• 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)