On the geometry of cyclic lattices

DOI10.1007/S00454-014-9608-3zbMATH Open1310.11071arXiv1406.4470OpenAlexW2129110547MaRDI QIDQ464733FDOQ464733

Authors: Lenny Fukshansky, Xun Sun 

Publication date: 29 October 2014

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

Abstract: Cyclic lattices are sublattices of $mathbb{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 $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.

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

Recommendations

• scientific article; zbMATH DE number 3922766
• Cyclic and well-rounded lattices
• Geometry of biquadratic and cyclic cubic log-unit lattices
• scientific article; zbMATH DE number 4002189
• scientific article; zbMATH DE number 992924
• Geometric constructions on cycles
• On the geometry of nearly orthogonal lattices
• scientific article; zbMATH DE number 802711
• scientific article; zbMATH DE number 5130043
• Über Gitter in der hyperbolischen Ebene.

zbMATH Keywords

well-rounded latticescyclic latticesshortest vector problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Generalized compact knapsacks, cyclic lattices, and efficient one-way functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Post-Quantum Cryptography
• Title not available (Why is that?)
• Computational geometry of positive definite quadratic forms. Polyhedral reduction theories, algorithms, and applications
• Minkowski’s conjecture, well-rounded lattices and topological dimension
• Making NTRU as secure as worst-case problems over ideal lattices
• Generalized Compact Knapsacks Are Collision Resistant
• Title not available (Why is that?)
• Theory of Cryptography
• On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications
• Minkowski Reduction of Integral Matrices
• On the complexity of decoding lattices using the Korkin-Zolotarev reduced basis
• Title not available (Why is that?)
• Sieving for shortest vectors in ideal lattices
• On Nearly Orthogonal Lattice Bases and Random Lattices
• Frobenius problem and the covering radius of a lattice

Cited In (19)

• Title not available (Why is that?)
• On Eulerian irregularities of prisms, grids and powers of cycles
• Bouquets of geometric lattices: Some algebraic and topological aspects
• Geometric construction of a coboundary of a cycle
• Title not available (Why is that?)
• Erratum to: ``On the geometry of cyclic lattices
• Title not available (Why is that?)
• Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
• Permutation invariant lattices
• Title not available (Why is that?)
• Title not available (Why is that?)
• The geometry of cyclic hyperbolic polygons
• Counting co-cyclic lattices
• On Lattices Generated by Finite Abelian Groups
• On the SVP for low-dimensional circulant lattices
• Discrete Lattices on the Single Bearing Spiral: From Geometry to Botany
• Cyclic and well-rounded lattices
• Cycle construction and geodesic cycles with application to the hypercube
• The linear transformation that relates the canonical and coefficient embeddings of ideals in cyclotomic integer rings

Uses Software

• NTRU
• NTRUSign

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)