NDLI: On the Geometry of Cyclic Lattices

Content Provider	Springer Nature Link
Author	Sun, Xun Fukshansky, Lenny
Copyright Year	2014
Abstract	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.
Ending Page	259
Page Count	20
Starting Page	240
File Format	PDF
ISSN	01795376
e-ISSN	14320444
Journal	Discrete & Computational Geometry
Issue Number	2
Volume Number	52
Language	English
Publisher	Springer US
Publisher Date	2014-08-06
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Quadratic forms (reduction theory, extreme forms, etc.) Well-rounded lattices Computational Mathematics and Numerical Analysis Cyclic lattices Lattices and convex bodies Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Combinatorics Shortest vector problem
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Theoretical Computer Science Computational Theory and Mathematics Geometry and Topology

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the geometry of cyclic lattices

On well-rounded ideal lattices - II

On integral well-rounded lattices in the plane

Monotonicity testing and shortest-path routing on the cube

On Integral Well-rounded Lattices in the Plane

Counting with rational generating functions

Well-rounded zeta-function of planar arithmetic lattices

New degree bounds for polynomial threshold functions

Two Remarks Concerning Balanced Matroids

On the Geometry of Cyclic Lattices

Similar Documents

On the geometry of cyclic lattices

On well-rounded ideal lattices - II

On integral well-rounded lattices in the plane

Monotonicity testing and shortest-path routing on the cube

On Integral Well-rounded Lattices in the Plane

Counting with rational generating functions

Well-rounded zeta-function of planar arithmetic lattices

New degree bounds for polynomial threshold functions

Two Remarks Concerning Balanced Matroids

On the Geometry of Cyclic Lattices