On The Geometry of Cyclic Lattices
Abstract
Cyclic lattices are sublattices of ZN that are preserved under the rotational shift operator. Cyclic lattices were introduced by D. Micciancio in [16] and their properties were studied in the recent years by several authors due to their importance in cryptography. In particular, Peikert and Rosen [19] showed that on cyclic lattices in prime dimensions, the shortest independent vectors problem SIVP reduces to the shortest vector problem SVP with a particularly small loss in approximation factor, as compared to general lattices. In this paper, we further investigate geometric properties of cyclic lattices, proving that a positive proportion of them in every dimension is well-rounded. One implication of our main result is that SVP is equivalent to SIVP on a positive proportion of cyclic lattices in every dimension. As an example, we demonstrate an explicit construction of a family of cyclic lattices on which this equivalence holds. To conclude, we introduce a class of sublattices of ZN closed under the action of subgroups of the permutation group SN , which are a natural generalization of cyclic lattices, and show that our results extend to all such lattices closed under the action of any N-cycle.
