Cyclic lattices are sublattices of \(\mathbb Z^N\) that are preserved under the rotational shift operator. Cyclic lattices were introduced by Micciancio (FOCS, IEEE Computer Society, pp 356–365, 2002) and their properties were studied in the recent years by several authors due to their importance in cryptography. In particular, Peikert and Rosen (Theory of Cryptography, Lecture Notes in Computer Science, vol 3876. Springer, Berlin, pp 145–166, 2006) 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 \(\mathbb Z^N\) closed under the action of subgroups of the permutation group \(S_N\), 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.
['Lenny Fukshansky', 'Xun Sun']
On the geometry of cyclic lattices