On the complexity of decoding lattices using the Korkin-Zolotarev reduced basis

Upper and lower bounds are derived for the decoding complexity of a general lattice L. The bounds are in terms of the dimension n and the coding gain gamma of L, and are obtained based on a decoding algorithm Which is an improved version of Kannan's method, The tatter is currently the fastest known method for the decoding of a general lattice, For the decoding of a point x, the proposed algorithm recursively searches inside an n-dimensional rectangular parallelepiped (cube), centered at x, With its edges along the Gram-Schmidt vectors of a proper basis of L. We call algorithms of this type recursive cube search (RCS) algorithms. It is shown that Kannan's algorithm also belongs to this category, The complexity of RCS algorithms is measured in terms of the number of lattice points that need to be examined before a decision is made, To tighten the upper bound on the complexity, We select a lattice basis which is reduced in the sense of Korkin-Zolotarev, It is shown that for any selected basis, the decoding complexity (using RCS algorithms) of any sequence of lattices with possible application in communications (gamma greater than or equal to 1) grows at least exponentially with n and gamma. It is observed that the densest lattices, and almost all of the lattices used in communications, e.g., Barnes-Wall lattices and the Leech lattice, have equal successive minima (ESR I). For the decoding complexity of ESM lattices, a tighter upper bound and a stronger loner bound result are derived.