Return to Colloquia & Seminar listing
On the geometry of cyclic lattices
Algebra & Discrete Mathematics| Speaker: | Lenny Fukshansky, Dept. of Mathematics, Claremont McKenna College |
| Location: | 1147 MSB |
| Start time: | Thu, Feb 21 2013, 3:10PM |
Cyclic lattices are sublattices of Z^N that are preserved under the rotational shift operator. They were introduced by Micciancio in 2002 and their properties were studied in the recent years by several authors due to their importance in cryptography. In particular, Peikert and Rosen (2005) proved that for cyclic lattices of prime dimension N, the short independent vectors problem SIVP reduces to (a slight variant of) the shortest vector problem SVP with only a factor of 2 loss in approximation factor (compared to the factor of N^{1/2} loss on general lattices). In this talk I will discuss certain geometric properties of cyclic lattices, showing that SVP is in fact equivalent to SIVP on a positive proportion of cyclic lattices in every dimension. Interestingly, it also turns out that on a positive proportion of cyclic lattices in every dimension the two problems are different.