On the Bases of Z^n Lattice

EasyChair Preprint 8862

Abstract

The Z^n lattice is the lattice generated by the set of all orthogonal unit integer vectors. Since it has an orthonormal basis, the shortest vector problem and the closest vector problem are easy to solve in this particular lattice. But, these problems are hard to solve when we consider a rotation of Z^n lattice. In-fact, even though it is known that the Z^n-isomorphism problem in NP \cap Co-NP, we still don't have an efficient algorithm to solve it. Motivated by the above, in this paper we investigate the properties of the bases of Z^n lattice which are the sets of column/row vectors of unimodular matrices. We show that an integer primitive vector of norm strictly greater than 1 can be extended to a unimodular matrix U such that the remaining vectors have norm strictly smaller than the initial primitive vector. We also show a reduction from SVP in any lattice isomorphic to Z^n to SVP in n-1 dimensional sublattice of Z^n. We define two new classes of lattice bases and show certain results related to Z^n bases. Finally, we study the relation between any solution to Successive Minima Problem and the set of Voronoi relevant vectors and present some bounds related to the compact bases of Z^n.

Keyphrases: Closest Vector Problem, Lattices, Shortest Vector Problem, Voronoi cell, Z^n isomorphism, lattice basis

@booklet{EasyChair:8862,
  author    = {Shashank Mehta and Mahesh Rajasree},
  title     = {On the Bases of Z^n Lattice},
  howpublished = {EasyChair Preprint 8862},
  year      = {EasyChair, 2022}}