A hierarchy of polynomial time lattice basis reduction algorithms

TLDR

The study introduces a hierarchy of polynomial‑time lattice basis reduction algorithms ranging from LLL to Korkine–Zolotareff, and improves Kannan’s algorithm for KZ reduction. The algorithm achieves a short vector b with |b|² ≤ (6k²)^{nk}λ(L)² by successively applying KZ reduction to k‑length blocks, using O(n²(k^k+o(k))+n²)log B arithmetic operations on O(n log B)-bit integers.

Abstract

We present a hierarchy of polynomial time lattice basis reduction algorithms that stretch from Lenstra, Lenstra, Lovász reduction to Korkine–Zolotareff reduction. Let λ(L) be the length of a shortest nonzero element of a lattice L. We present an algorithm which for k∈N finds a nonzero lattice vector b so that |b|2⩽(6k2)nkλ(L)2. This algorithm uses O(n2(kk+o(k))+n2)log B) arithmetic operations on O(n log B)-bit integers. This holds provided that the given basis vectors b1,…,bn∈Zn are integral and have the length bound B. This algorithm successively applies Korkine–Zolotareff reduction to blocks of length k of the lattice basis. We also improve Kannan's algorithm for Korkine-Zolotareff reduction.