On the geometry of cyclic lattices

DOI10.1007/S00454-014-9608-3MaRDI QIDQ464733zbMATH OpenOpenAlexFDO

Publication date 29 October 2014

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.4470

cyclic lattices shortest vector problem well-rounded lattices

Lattices and convex bodies (number-theoretic aspects) (11H06) Quadratic forms (reduction theory, extreme forms, etc.) (11H55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Cyclic lattices are sublattices of

m a t h b b Z^{N}

that are preserved under the rotational shift operator. Cyclic lattices were introduced by D.~Micciancio and their properties were studied in the recent years by several authors due to their importance in cryptography. In particular, Peikert and Rosen 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. Our main result is a counting estimate for the number of well-rounded cyclic lattices, indicating that well-rounded lattices are more common among cyclic lattices than generically. We also show that SVP is equivalent to SIVP on a positive proportion of Minkowskian well-rounded cyclic lattices in every dimension. As an example, we demonstrate an explicit construction of a family of such lattices on which this equivalence holds. To conclude, we introduce a class of sublattices of

m a t h b b 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.

Review text

Cyclic lattices are sublattices of \({\mathbb Z}^N\) that are preserved under the rotational shift operator, i.e., the operator that cyclically change basis vectors. In particular, cyclic lattices are of interest due to their applications in cryptography. In this paper the authors prove that a positive proportion of cyclic lattices in every dimension is well-rounded. As a consequence one has that the shortest vectors problem (SVP) is equivalent to the shortest independent vectors problem (SIVP) on a positive proportion of cyclic lattices in every dimension. Additionally the authors generalized these results to another class of sublattices of \({\mathbb Z}^N\) closed under the action of subgroups of the permutation group \(S_N\).

Recommendations

Cites work

Cited in

(20)

Describes a project that uses

Uses Software

This page was built for publication: On the geometry of cyclic lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q464733)