Korkine–Zolotarev lattice basis reduction algorithm: Difference between revisions

Revision as of 17:37, 11 December 2021

Latest revision as of 10:44, 9 September 2023

(23 intermediate revisions by 11 users not shown)

Line 1:

{{distinguish|Kolmogorov–Zurbenko filter}}

The '''Korkine–Zolotarev (KZ) lattice basis reduction algorithm''' is a [[lattice 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 [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|LLL reduction]] algorithm, it is preferred for solving sequences of [[Lattice problem|Closest Vector Problems]] (CVPs) in a lattice, where it may be more efficient.

For lattices in <math>\mathbb{R}^n</math> it yields a lattice basis with orthogonality defect at most <math>n^n</math>, unlike the <math>2^{n^2/2}</math> bound of the [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|LLL reduction]].<ref>https://sites.math.washington.edu/~rothvoss/lecturenotes/IntOpt-and-Lattices.pdf, pp. 18-19</ref> KZ has exponential complexity versus the polynomial complexity of the [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|LLL reduction]] algorithm, however it may still be preferred for solving multiple [[closest vector problem]]s (CVPs) in the same lattice, where it can be more efficient.

==History==

The definition of a KZ-reduced basis was given by A.[[Aleksandr KorkineKorkin]] and G.[[Yegor ZolotareffIvanovich Zolotarev]] in 1877, a strengthened version of [[Hermite normal form|Hermite reduction]]. The first algorithm for constructing a KZ-reduced basis was given in 1983 by Kannan.<ref>Zhang et al 2012, p.1</ref>

The '''block Korkine-Zolotarev''' ('''BKZ''') algorithm was introduced in 1987.<ref>{{Cite book|chapter-url=https://link.springer.com/chapter/10.1007/978-981-15-5191-8_15|doi = 10.1007/978-981-15-5191-8_15|chapter = A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge|title = International Symposium on Mathematics, Quantum Theory, and Cryptography|series = Mathematics for Industry|year = 2021|last1 = Yasuda|first1 = Masaya|volume = 33|pages = 189–207|isbn = 978-981-15-5190-1|s2cid = 226333525}}</ref>

==Definition==

Line 26 ⟶ 30:

:<math>\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</math>

which project <math>\mathbf{x}</math> orthogonally onto the span of <math>\mathbf{b}^*_i, \cdots, \mathbf{b}^*_n</math>.

Then the basis <math>B</math> is KZ-reduced if the following holds:

# <math>\mathbf{b}^*_i</math> is the shortest nonzero vector in <math>\pi_i(\mathcal{L}(\mathbf{B}))</math>

# For all <math>j < i</math>, <math>\left|\mu_{i,j}\right| \leq 1/2</math>

Note that the first condition can be reformulated recursively as stating that <math>\mathbf{b}_1</math> is a shortest vector in the lattice, and <math>\{\pi_2(\mathbf{b}_2), \cdots \pi_2(\mathbf{b}_n)\}</math> is a KZ-reduced basis for the lattice <math>\pi_2(\mathcal{L}(\mathbf{B}))</math>.

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.

NoteAlso 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==

Line 45 ⟶ 50:

|first2=G.|last2=Zolotareff

|title=Sur les formes quadratiques positives

|journal=Mathematische Annalen

|year=1877

|volume=11

|url=https://link.springer.com/article/10.1007/BF01442667

|issue=2

|pages=131-136}}242–292

|s2cid=121803621

|doi=10.1007/BF01442667

|url=https://arxivzenodo.org/pdfrecord/1703.03303.pdf1896288

}}

Line 52 ⟶ 63:

|first2=Cong|last2=Ling

|title=Boosted KZ and LLL Algorithms

|journal=IEEE Transactions on Signal Processing

|year=2017

|volume=65

|url=https://arxiv.org/pdf/1703.03303.pdf

|issue=18

|pages=4784–4796

|doi=10.1109/TSP.2017.2708020

|arxiv=1703.03303

|bibcode=2017ITSP...65.4784L

|s2cid=16832357

}}

Line 59 ⟶ 77:

|title=On the KZ Reduction

|year=2018

|urlarxiv=https://arxiv.org/pdf/1702.08152.pdf}}

}}

* {{cite book|first1=Daniele|last1=Micciancio|

Line 66 ⟶ 83:

|title=Complexity of Lattice Problems

|year=2002

|pages=131–136

|urldoi=https://link.springer.com/book/10.1007/978-1-4615-0897-7

|pages=131-136}}

|isbn=978-1-4613-5293-8}}

* {{cite journal|first1=Wen|last1=Zhang|first2=Sanzheng|last2=Qiao|first3=Yimin|last3=Wei

|title=HKZ and Minkowski Reduction Algorithms for Lattice-Reduction-Aided MIMO Detection

|journal=IEEE Transactions on Signal Processing |year=2012

|year=2012

|volume=60 |issue=11 |page=5963 |doi=10.1109/TSP.2012.2210708 |bibcode=2012ITSP...60.5963Z |s2cid=5962834 |url=http://www.cas.mcmaster.ca/~qiao/publications/ZQW12a.pdf

}}

Line 78 ⟶ 96:

{{Number-theoretic algorithms}}

{{DEFAULTSORT:Korkine-Zolotarev lattice basis reduction algorithm}}

[[Category:Theory of cryptography]]

[[Category:Computational number theory]]