Complexity of lattice problems on cyclic lattices

04/23/2013 - 12:15pm
04/23/2013 - 1:10pm
Lenny Fukshansky (CMC)

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. Further, these results naturally generalize to a class of lattices invariant under the action of certain subgroups of the permutation group S_N. This is joint work with Xun Sun (CGU).

Millikan 208 (Pomona College)