Mathematics Colloquia and Seminars

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.